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.

存在一棵带权树 $T$，其包含 $N$ 个编号为 $1$ 至 $N$ 的顶点。树 $T$ 的第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，权重为 $C_i$。

现在，我们基于 $T$ 构造一个包含 $N$ 个编号为 $1$ 至 $N$ 的顶点的无向完全图 $G$。对于 $G$ 中的每条边，其容量定义如下：

• 图 $G$ 中边 $(i,j)$ 的容量等于树 $T$ 上连接顶点 $i$ 和 $j$ 的路径中所含边的最小权重。

令 $f(i,j)$ 表示图 $G$ 中分离顶点 $i$ 和 $j$ 的最小割的容量。

求 $\sum_{1 \leq i < j \leq N} f(i,j)$ 对 $998244353$ 取模的结果。

对每组输入，需解决 $S$ 个测试用例。

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}$

输入从标准输入中按以下格式给出：

$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}$

For each test case, output the answer.

对于每个测试用例，输出答案。

Sample 1 Explanation:
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.

样例 1 解释：
在第一个测试用例中，图 $G$ 中边 $(1,2)$、$(1,3)$、$(2,3)$ 的容量分别为 $1$、$1$、$10$。答案为 $f(1,2)+f(1,3)+f(2,3)=2+2+11=15$。

约束条件

• $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$。
• 所有输入值均为整数。