「この任務は永遠に完了できない。私は二度と同じ過ちを繰り返さない。」 「愛と感情を理解した彼は、もはやロボットではない……その観点から見れば、3000Aは君の息子だ、霍星。」 —— さらば、3000A！『魔角偵探』
$n$ 個のノードからなる木と、$m$ 本のパス $(u, v, w)$ が与えられる。ここで $w$ はパス $(u, v)$ に付与された重みとみなす。パスの集合 $S$ の重み $W(S)$ を次のように定義する：$S$ の部分集合のうち、どの2つのパスも共通の頂点を持たないようなもののうち、重みの総和が最大となるものを探し、その重みの総和を $W(S)$ とする。
$f(u, v) = w$ を、与えられた $m$ 本の辺からなるパス集合 $U$ に対して $W(U \cup \{(u, v, w + 1)\}) > W(U)$ を満たす最小の非負整数 $w$ と定義する。
以下の式の値を $998244353$ で割った余りを計算せよ。
$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$
入力形式
1行目に2つの整数 $n, m$ が与えられる。これらは木のノード数と与えられたパスの数である。
続く $n-1$ 行には、木の辺を表す2つの整数 $u, v$ が与えられる。
続く $m$ 行には、集合に追加されるパスの端点 $u, v$ とその重み $w$ を表す3つの整数 $u, v, w$ が与えられる。
出力形式
答えを1つの整数で出力せよ。
入出力例
入力 1
4 4 1 2 1 3 1 4 1 2 1 3 3 2 1 4 3 2 4 6
出力 1
100
注記
$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$
サブタスク
| テスト点 | $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$ |