Wormhole Logistics Optimization

In the year \(2044\), humanity has entered the cosmic era. In country L there are \(n\) planets connected by \(n-1\) bi‐directional space routes (edges) that form a tree. A logistics company has pre-booked \(m\) transportation plans. Each plan requires a spaceship to travel from planet \(u_i\) to planet \(v_i\) along the unique shortest path in the tree. Every edge \(j\) takes \(t_j\) time to traverse, and there is no interference between the spaceships.

The king of country L allows the company to convert exactly one edge into a wormhole. In a wormhole, the traversal time becomes zero. Once the wormhole is constructed, all \(m\) transportation plans start simultaneously, and the company finishes its stage work only when the slowest shipment completes its journey.

If you can choose any edge to convert into a wormhole, determine the minimum possible time by which all shipments can finish.

The answer should be computed as follows. Suppose for a candidate edge \(j\) (with weight \(t_j\)) that splits the tree into two parts. A shipment will traverse \(j\) (and hence save \(t_j\) time) if its start and end planets lie in different components; otherwise, its travel time remains unchanged. Let \(d_i\) be the original travel time of the \(i\)th shipment. Then when using edge \(j\) as a wormhole, the travel time for shipment \(i\) is given by:

[ T_i = \begin{cases} d_i - t_j, & \text{if shipment } i \text{ crosses edge } j,\ d_i, & \text{otherwise.} \end{cases} ]

Your task is to select an edge \(j\) so that the maximum \(T_i\) (over all shipments) is minimized. Output this minimum possible maximum time.

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n, ~ m \ge 1)\), representing the number of planets and the number of transportation plans.

The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(t\) \((1 \le u,v \le n, ~ t \ge 1)\), indicating there is a bi-directional route between planets \(u\) and \(v\) with travel time \(t\).

The next \(m\) lines each contain two integers \(u_i\) and \(v_i\) \((1 \le u_i,v_i \le n)\), representing a transportation plan from planet \(u_i\) to planet \(v_i\).

outputFormat

Output a single integer: the minimum possible maximum travel time among all \(m\) shipments if you choose the best possible edge to convert into a wormhole.

sample

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

5