AT_awtf2026algo_a Min Cut of Graph of Min Weight

There is a weighted tree $ T $ with $ N $ vertices numbered $ 1 $ to $ N $ . The $ i $ -th edge of $ T $ connects vertices $ A_i $ and $ B_i $ with weight $ C_i $ . We now construct a complete undirected graph $ G $ with $ N $ vertices numbered $ 1 $ to $ N $ , based on $ T $ . For each edge of $ G $ , the capacity is defined as follows. - The capacity of edge $ (i,j) $ of $ G $ is the minimum weight of an edge contained in the path connecting vertices $ i $ and $ j $ on $ T $ . Let $ f(i,j) $ be the capacity of the minimum cut separating vertices $ i $ and $ j $ on $ G $ . Find $ \sum_{1 \leq i < j \leq N} f(i,j) $ , modulo $ 998244353 $ . Solve $ S $ cases for each input.

The input is given from Standard Input in the following format: > $ S $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_S $ Each test case is given in the following format: > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

For each test case, output the answer.

### Sample Explanation 1 In the first test case, the capacities of edges $ (1,2),(1,3),(2,3) $ of $ G $ are $ 1,1,10 $ , respectively. The answer is $ 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} $ - The input graph is a tree. - The sum of $ N $ over the $ S $ cases is at most $ 250000 $ . - All input values are integers.