题目描述

你有一个含$\red{n}$个点，$\red{m}$条边的图。现在选出一棵生成树，你每次可以选择树上一条边使其边权$\red{-1，}$问至少需要操作多 少次之后这棵树会成为图的最小生成树？保证图完全连通且不含重边。

注：图中节点编号从$\red{1 \sim n}$。

输入格式

第一行输入两个数$\red{n,m，}$分别表示图的点数和边数；（$\red{1≤}$$\red{n≤}$$\red{10000，}$$\red{1≤}$$\red{m≤}$$\red{100000）}$

之后$\red{m}$行，每行三个数$\red{u,v,w，}$表示从点$\red{u}$到点$\red{v}$的连边权值为$\red{w}$；

之后$\red{n-1}$行，每行两个数$\red{a,b，}$表示选定生成树的每条边。

输出格式

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

样例

输入样例

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

提示

样例中的情况如图所示，对于选定的树，只要将$\red{3-4}$边的权值改为$\red{2}$即可成为最小生成树，操作次数为$\red{5}$。

对于$\red{25\%}$的数据，$\red{1≤}$$\red{n≤}$$\red{20，}$$\red{1≤}$$\red{m≤}$$\red{100}$；

对于$\red{40\%}$的数据，$\red{1≤}$$\red{n≤}$$\red{100，}$$\red{1≤}$$\red{m≤}$$\red{500}$；

对于$\red{60\%}$的数据，$\red{1≤}$$\red{n≤}$$\red{1000，}$$\red{1≤}$$\red{m≤}$$\red{5000}$；

对于$\red{100\%}$的数据，$\red{1≤}$$\red{n≤}$$\red{10000，}$$\red{1≤}$$\red{m≤}$$\red{100000，}$$\red{1≤}$$\red{w≤}$$\red{1000000，}$$\red{1≤}$$\red{a,b<=n}$；