暂无测试数据。

众所周知，C 爷爷和 B 爷爷是给给专业户

某一天，C 爷爷发现 B爷爷开了一家物流运输店！OI 水平干爆一切的 C 爷爷决定要不用脑子地帮 B 爷爷优化他的物流线路。由于 B 爷爷喜欢精简，所以他的物流公司路线用 $n-1$ 条双向带权路径连接了 $n$ 个点，并且任意两点之间都肯定是联通的啦。

对于一个物流线路 $x->y$， B爷爷规定他的花费是图上 $x$ 到 $y$ 的所有路径中的边的最大值

C爷爷只能选择其中的一条边并对其施放魔法，魔法很奇特，假如对于某条路线 $x_i$,$y_i$ ，他经过了这条边并且路径最大值等于这条边的权，那么这个路线的花费就变为了路径中所有边的严格次大值，注意不是次大值，而是严格次大

当然的，C爷爷想要所有线路的花费和最小

由于C爷爷不想动脑他还要切翻今年的IOIIONOIPACSTC

所以他就把这个任务交给你啦

输入格式

输入第一行包含两个数 $n,m$ 分别表示图的点数与物流线路的数量

接下来 $n-1$ 行每行三个数 $x,y,c$ 表示图上有一个从 $x$ 到 $y$ 的边权为 $c$ 的路径

接下来 $m$ 行每行两个数 $x,y$ 表示 B 爷爷拥有一条从 $x$ 到 $y$ 的物流路径

输出格式

一行一个数表示最小花费和

数据范围

对于 $30\%$ 的数据，保证 $n\leq 100$ ， $m\leq 100$

对于 $60\%$ 的数据，保证 $n\leq 10^5$ ， $m\leq 10^5$

对于 $100\%$ 的数据，保证 $n\leq 10^5$ ， $m\leq 5*10^5$ ， $c\leq 10^6$ ，保证不存在起点与终点相同的物流路径

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

5