给定一个简单图 $G=(V,E,W)$，$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$:
$S=\sum_{e \in E} \Delta(e)$
第一行为 $N$、$M$，其中 $N$ 表示顶点的数目，$M$ 表示边的数目。顶点的编号为 $1$、$2$、$3$、……、$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$ 的一条边。
输出最小权值。
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
$1 \le N \le 50，1 \le M \le 800，1 \le W_i \le 1000$
Comet OJ