qym 的最小生成树

题目描述

qym 最近学习了最小生成树，这天他画了一个含 $n$ 个点，编号为 $1 \sim n$， $m$ 条边的图。

但是他的代码写错了，他的代码输出的这棵树并不是这张图的最小生成树。

为了让代码的答案是正确的，qym 决定修改一下代码输出的这棵树上的一些边

他每次会选择树上的一条边使其边权 $-1$

qym 想知道至少需要操作多少次之后他的答案是正确的？即这棵树会成为这张图的最小生成树？

保证图完全连通且不含重边。

输入格式

第一行输入两个数 $n,m$ ，分别表示图的点数和边数 之后m行，每行三个数 $u,v,w$，表示从点 $u$ 到点 $v$ 的连边权值为 $w$ 之后 $n-1$ 行，每行两个数 $a,b$ ，表示选定生成树的每条边。

输出格式

输出一个数，表示最少的操作次数。

数据范围

对于 $25\%$ 的数据，满足 $1 \leq n \leq 20, 1 \leq m \leq 100$ 对于 $40\%$ 的数据，满足 $1 \leq n \leq 100, 1 \leq m \leq 500$ 对于 $60\%$ 的数据，满足 $1 \leq n \leq 1000, 1 \leq m \leq 5000$ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 10000, 1 \leq m \leq 10^5, 1 \leq w \leq 10^6, 1 \leq a,b \leq n$ 。

样例输入

5 7
1 2 5
1 3 3
1 4 1
1 5 2
2 3 2
3 4 4
4 5 7
2 3
3 1
1 4
4 5

样例输出

5

样例解释

将 $4-5$ 这条边的边权 $-5$，即可成为最小生成树