„To zadanie nigdy nie zostanie ukończone. Nie popełnię ponownie tego samego błędu.”

„Zrozumiawszy miłość i emocje, nie jest już robotem... Z tego punktu widzenia 3000A jest twoim synem, Huo Xing.”

—— Żegnaj, 3000A! „Detective 3000A”

Dane jest drzewo o $n$ wierzchołkach oraz $m$ ścieżek $(u, v, w)$, gdzie $w$ można uznać za wagę przypisaną do ścieżki $(u, v)$. Wagę zbioru ścieżek $S$, oznaczaną jako $W(S)$, definiuje się jako sumę wag podzbioru ścieżek z $S$ o maksymalnej sumie wag, przy założeniu, że żadne dwie ścieżki w tym podzbiorze nie mają wspólnych wierzchołków.

Niech $f(u, v) = w$ będzie najmniejszą nieujemną liczbą całkowitą $w$ taką, że dla danego zbioru ścieżek $U$ złożonego z $m$ krawędzi, zachodzi $W(U \cup \{(u, v, w + 1)\}) > W(U)$.

Oblicz poniższą sumę modulo $998244353$:

$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n, m$, oznaczające liczbę wierzchołków drzewa oraz liczbę podanych ścieżek.

W kolejnych $n-1$ liniach znajdują się dwie liczby całkowite $u, v$ oznaczające krawędź drzewa.

W kolejnych $m$ liniach znajdują się trzy liczby całkowite $u, v, w$, oznaczające dodanie do zbioru ścieżki o końcach $u, v$ oraz jej wagę.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą wynik.

Przykład

Wejście 1

4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6

Wyjście 1

100

Uwagi

$f(1, 1) = 6, f(1, 2) = 6, f(1, 3) = 8, f(1, 4) = 6$

$f(2, 1) = 6, f(2, 2) = 3, f(2, 3) = 8, f(2, 4) = 6$

$f(3, 1) = 8, f(3, 2) = 8, f(3, 3) = 2, f(3, 4) = 8$

$f(4, 1) = 6, f(4, 2) = 6, f(4, 3) = 8, f(4, 4) = 5$

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$.