[SHOI2004] 最小生成树

题目描述

给定一个筒单图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=\sum_{e \in E} \Delta(e)$

输入输出格式

输入格式


第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

输出格式


输出最小权值

输入输出样例

输入样例 #1

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

输出样例 #1

8

说明

【样例说明】 边(4,6)的权由7修改为3,代价为4 边(1,2)的权由2修改为3,代价为1 边(1,5)的权由1修改为4,代价为3 所以总代价为4+1+3=8 修改方案不唯一。 1<=n<=50,1<=m<=1500,1<=wi<=1000 n-->点数..m-->边数..wi--->边权