Description

Given a simple graph $G=\langle V, E, W \rangle$, where $V$ is the set of vertices, $E$ is the set of edges (no multiple edges; i.e., there is at most one edge between any two vertices), and $W$ is an integer-valued weight function defined on $E$. A spanning tree $T$ on $G$ is given. Modify $W$ with the minimum total cost so that $T$ becomes a minimum spanning tree on $G$ (a graph may have multiple minimum spanning trees; it suffices that the sum of edge weights of $T$ is minimum). For any edge $e \in E$, the modification rules are:

• Increase the weight of $e$: set $W'(e) = W(e) + \Delta(e)$, and the cost to modify this edge is $\Delta(e)$.
• Decrease the weight of $e$: set $W'(e) = W(e) - \Delta(e)$, and the cost to modify this edge is $\Delta(e)$.
• Do not change the weight of $e$: set $W'(e) = W(e)$, with modification cost $\Delta(e)=0$.

Note: The modified weight function $W'$ also takes integer values.

The total modification cost is $S = \sum\limits_{e \in E} \Delta(e)$.

Input Format

The first line contains $N, M$, where $N$ is the number of vertices and $M$ is the number of edges. Vertices are numbered $1, 2, 3, \dots, N-1, N$.

The next $M$ lines each contain three integers $U_i, V_i, W_i$, indicating there is an edge between vertices $U_i$ and $V_i$ with weight $W_i$.

Each edge appears exactly once in the input. Then, the next $N-1$ lines each contain two integers $X_i, Y_i$, indicating that the edge between $X_i$ and $Y_i$ is an edge of $T$.

Output Format

Output the minimum $S$.

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

8

Hint

Edge $(4,6)$ has its weight changed from $7$ to $3$, with cost $4$;
edge $(1,2)$ has its weight changed from $2$ to $3$, with cost $1$;
edge $(1,5)$ has its weight changed from $1$ to $4$, with cost $3$.

Therefore, the total cost is $4+1+3=8$.

Constraints: $1 \le N \le 50$, $1 \le M \le 1500$, $1 \le W_i \le 1000$.

Translated by ChatGPT 5