题目描述

给定一个筒单图 $G=\langle V.E.W\rangle$，$V$ 为顶点集合，$E$ 为边的集合（无重边，即任意两个顶点之间至多只有一条边)，$W$ 为定义在 $E$ 上的权函数（值为整数)。给出其上的一棵生成树 $T$，现在要求用最小的代价修改 $W$，使得 $T$ 是 $G$ 上的一棵最小生成树（一个图可以有多棵最小生成树，只要 $T$ 的边权和最小即可)。对于任意一条边 $e \in E$ 修改方法为：

• 增加 $e$ 的权值，即令 $W'(e)=W(e)+\Delta(e)$，则修改该边的代价为 $\Delta(e)$
• 减小 $e$ 的权值，即令 $W'(e)=W(e)-\Delta(e)$，则修改该边的代价为 $\Delta(e)$
• 不改变 $e$ 的权，即 $W'(e)=W(e)$，修改代价为 $\Delta(e)=0$。

请注意：修改后的权函数 $W'$ 的值域也为整数。

总的修改代价记为 $S=\sum\limits_{e \in E} \Delta(e)$。

输入格式

第一行为 $N,M$，其中 $N$ 表示顶点的数目，$M$ 表示边的数目。顶点的编号为 $1,2,3,\cdots,N-1,N$。

接下来的 $M$ 行，每行三个整数 $U_i,V_i,W_i$，表示顶点 $U_i$ 与 $V_i$ 之间有一条边，其权值为 $W_i$。

所有的边在输入中会且仅会出现一次。再接着 $N-1$ 行，每行两个整数 $X_i,Y_i$，表示顶点 $X_i$ 与 $Y_i$ 之间的边是 $T$ 的一条边。

输出格式

输出最小的 $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

提示

边 $(4,6)$ 的权由 $7$ 修改为 $3$，代价为 $4$；
边 $(1,2)$ 的权由 $2$ 修改为 $3$，代价为 $1$；
边 $(1,5)$ 的权由 $1$ 修改为 $4$，代价为 $3$；

所以总代价为 $4+1+3=8$。

$1 \le N \le 50,1 \le M \le 1500,1 \le W_i \le 1000$。