题目描述

公元 $2150$ 年，人类迈入星际时代。

某个星域里有 $n$ 个空间站，以及 $n-1$ 条双向航道，每条航道连接两个空间站，这 $n-1$ 条航道恰好把所有空间站连通在一起。

小 K 经营着一家星际货运公司，手头有许多份运输订单，每份订单的内容是：一艘货运飞船需要从 $u_i$ 号空间站沿最快的航路飞往 $v_i$ 号空间站。显然，飞船经过航道是要花时间的，对于航道 $j$，任何飞船经过它都要花费 $t_j$ 的时间，而任意两艘飞船之间不会产生任何干扰。

为了鼓励技术革新，星域管理方特许小 K 的公司参与航道改造：小 K 可以把恰好一条航道升级成虫洞，飞船经过虫洞不消耗任何时间。

在虫洞动工之前，公司就已经接下了 $m$ 份运输订单。虫洞建成之后，这 $m$ 份订单会同时开始执行，所有飞船一齐出发；当这 $m$ 份订单全部完成时，公司这一阶段的任务就算结束了。

如果小 K 可以任选一条航道升级成虫洞，请你求出公司完成这一阶段任务所需的最短时间是多少。

输入格式

第一行包括两个正整数 $n, m$，表示星域中空间站的数量和公司已接订单的数量，空间站从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个空间站之间，任何飞船经过它都要花费 $t_i$ 的时间。

接下来 $m$ 行描述订单情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$，表示第 $j$ 份订单是从 $u_j$ 号空间站飞往 $v_j$ 号空间站。

输出格式

一个整数，表示公司完成这一阶段任务所需要的最短时间。

样例

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

11

提示

数据范围与约定

各测试点规模不等，最小的测试点 $n = 100, m = 1$，最大的测试点 $n = 300000, m = 300000$；部分测试点保证第 $i$ 条航道恰好连接 $i$ 号与 $i + 1$ 号空间站。

对于 $100\%$ 的数据，$1 \le a_i, b_i, u_j, v_j \le n$，$0 \le t_i \le 1000$。

请注意常数因子带来的程序效率上的影响。