Description

In the year $2044$, humanity entered the cosmic era.

Country L has $n$ planets and $n-1$ bidirectional routes. Each route is built between two planets, and these $n-1$ routes connect all the planets in Country L.

Xiao P runs a logistics company that has many transportation plans. Each plan is as follows: a cargo spaceship needs to travel from planet $u_i$ to planet $v_i$ along the fastest space route. Obviously, traversing a route takes time. For route $j$, any spaceship takes time $t_j$ to traverse it, and any two spaceships do not interfere with each other.

To encourage technological innovation, the king of Country L allows Xiao P’s logistics company to participate in route construction, that is, to transform one route into a wormhole. Traversing the wormhole takes no time.

Before the wormhole is completed, Xiao P’s company has already pre-booked $m$ transportation plans. After the wormhole is completed, these $m$ plans will start simultaneously, and all spaceships depart together. When all $m$ plans are completed, Xiao P’s company finishes this phase of work.

If Xiao P can freely choose which route to convert into a wormhole, find the minimum time required for the company to complete this phase of work.

Input Format

The first line contains two positive integers $n, m$, representing the number of planets in Country L and the number of transportation plans pre-booked by Xiao P’s company. Planets are numbered from $1$ to $n$.

The next $n-1$ lines describe the construction of the routes. The $i$-th line contains three integers $a_i, b_i$, and $t_i$, indicating that the $i$-th bidirectional route is built between planets $a_i$ and $b_i$, and any spaceship takes time $t_i$ to traverse it.

The next $m$ lines describe the transportation plans. The $j$-th line contains two positive integers $u_j$ and $v_j$, indicating that the $j$-th plan is to travel from planet $u_j$ to planet $v_j$.

Output Format

Output one integer, the minimum time required for Xiao P’s logistics company to complete this phase of work.

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

11

Hint

The Constraints and characteristics of all testdata are shown in the table below.

Please pay attention to the impact of constant factors on program efficiency.

Translated by ChatGPT 5