“這個任務永遠無法完成。我不會再重複同樣的錯誤。” “懂得了愛與情感的他，早已經不是機器人了……從這個角度上看，3000A 就是你的兒子，霍星。” —— 永別，3000A！《魔角偵探》
給你一顆 $n$ 個節點的樹，以及 $m$ 條路徑 $(u, v, w)$，其中 $w$ 可以認為是 $(u, v)$ 這條路徑被標記的一個權值。一個路徑集合 $S$ 的重量 $W(S)$ 記為：找出 $S$ 的一個權值之和最大的子集，該子集滿足任何兩條路徑沒有公共點，這個子集的所有路徑權值之和就是 $W(S)$。
記 $f(u, v) = w$ 為最小的非負整數 $w$，使得對於給定的 $m$ 條邊組成的路徑集合 $U$，$W(U \cup \{(u, v, w + 1)\}) > W(U)$。
請你計算下式，對 $998244353$ 取模。
$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$
輸入格式
第一行輸入兩個整數 $n, m$，表示樹的節點數量以及給出的路徑數量。
接下來 $n-1$ 行，每行輸入兩個整數 $u, v$ 表示樹的一條邊。
接下來 $m$ 行，每行輸入三個整數 $u, v, w$，表示在集合中加入這條 $u, v$ 為端點的路徑以及其權值。
輸出格式
輸出一個整數表示答案。
範例
範例輸入 1
4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6範例輸出 1
100說明 1
$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$
資料範圍
對於 $100\%$ 的資料，保證 $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$。
| 測試點 | $n,m$ | 特殊性質 |
|---|---|---|
| $1,2$ | $=10$ | |
| $3$ | $=40$ | |
| $4$ | $=150$ | |
| $5,6$ | $=350$ | |
| $7,8$ | $=1,500$ | |
| $9,10$ | $=3,499$ | 樹的結構 $v=u+1$ |
| $11,12$ | $=3,500$ | |
| $13,14$ | $=99,995$ | 給出的路徑 $u=v$ |
| $15,16$ | $=99,996$ | 給出的路徑 $w=1$ |
| $17,18$ | $=99,997$ | 樹的結構 $v=u+1$ |
| $19,20$ | $=99,998$ | 樹的結構 $u=1$ |
| $21,22,23$ | $=99,999$ | 樹的結構 $u = \lfloor v/2\rfloor$ |
| $24$ | $=10^5$ | |
| $25$ | $=3\times10^5$ |