AT_awtf2026algo_a Min Cut of Graph of Min Weight

$ 1 $ から $ N $ までの番号のついた $ N $ 頂点からなる重み付き木 $ T $ があります． $ T $ の $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ重み $ C_i $ の辺です． 今から $ T $ を元に， $ 1 $ から $ N $ までの番号のついた $ N $ 頂点からなる完全無向グラフ $ G $ を作ります． $ G $ の各辺に対し，次のように容量を定めます． - $ G $ の辺 $ (i,j) $ の容量は， $ T $ 上で頂点 $ i $ と頂点 $ j $ を結ぶパスに含まれる辺の重みの最小値とする． $ G $ 上で頂点 $ i $ と頂点 $ j $ を分離する最小カットの容量を $ f(i,j) $ とします． $ \sum_{1 \leq i < j \leq N} f(i,j) $ を $ 998244353 $ で割った余りを求めてください． $ 1 $ つの入力につき， $ S $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ S $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_S $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

各テストケースについて，答えを出力せよ．

### Sample Explanation 1 $ 1 $ つ目のテストケースでは， $ G $ の辺 $ (1,2),(1,3),(2,3) $ の容量はそれぞれ $ 1,1,10 $ です． そして答えは $ f(1,2)+f(1,3)+f(2,3)=2+2+11=15 $ です． ### Constraints - $ 1 \leq S \leq 125000 $ - $ 2 \leq N \leq 250000 $ - $ 1 \leq A_i,B_i \leq N $ - $ 1 \leq C_i \leq 10^{12} $ - 入力されるグラフは木である - $ S $ ケースにわたる $ N $ の総和は $ 250000 $ 以下 - 入力はすべて整数