题目描述

Bob 的城市里有 $n$ 个邮递站，由于经济考虑，这些邮递站被 $n - 1$ 条带权无向边相连。即：这 $n$ 个邮递站构成了一棵树。

Bob 正在应聘一个快递员的工作，他需要送 $m$ 个商品，第 $i$ 个商品需要从 $u$ 送到 $v$。由于 Bob 不能带着商品走太长的路，所以对于一次送货，他需要先从快递中心到 $u$，再从 $u$ 回到快递中心，再从快递中心到 $v$，最后从 $v$ 返回快递中心。换句话说，如果设快递中心是 $c$ 号点，那么他的路径是 $c \rightarrow u \rightarrow c \rightarrow v \rightarrow c$。

现在 Bob 希望确定一个点作为快递中心，使得他送货所需的最长距离最小。显然，这个最长距离是个偶数，你只需要输出最长距离除以 $2$ 的结果即可。

输入格式

第一行输入两个数 $n, m$，意义如上。

接下来 $n-1$ 行，每行三个数 $u_i, v_i, w_i$，表示一条连接 $u_i, v_i$，长度为 $w_i$ 的边。

接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示商品的起止位置。

输出格式

一行一个整数，表示答案。

3 1
1 2 1
2 3 1
1 3

2

提示

对于 $25\%$ 的数据，满足 $1 \leq n, m \leq 1000$。

对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 10^5, 1 \leq w_i \leq 1000$。