Blink Inspection

There are $N$ traffic lights and $N-1$ wires. The lights are numbered $1,2,\cdots,N$, and the wires connect them as a tree.

Each light has state $0$ or $1$. Every wire must be inspected exactly once, and the inspection order may be chosen freely.

Inspecting a wire with endpoints $u,v$ performs the following actions in order:

1. If the states of lights $u$ and $v$ differ immediately before the inspection, pay this wire's cost.
2. Then flip both states. State $0$ becomes $1$, and state $1$ becomes $0$.

Find the minimum total cost paid while inspecting every wire.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$ $u_1\ v_1\ C_1$ $u_2\ v_2\ C_2$ $\vdots$ $u_{N-1}\ v_{N-1}\ C_{N-1}$

$S_i$ is the initial state of light $i$.

For each test case, print the minimum total cost of inspecting every wire exactly once.

• $1 \leq T \leq 150\,000$.
• $2 \leq N \leq 300\,000$.
• $S_i\in\{0,1\}$ ($1 \leq i \leq N$).
• $1 \leq u_i,v_i \leq N$, $u_i\neq v_i$ ($1 \leq i \leq N-1$).
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N-1$).
• The given wires form a tree.
• The sum of $N$ over all test cases does not exceed $300\,000$.