In the year 2044, humanity has entered the space age. Country L has $n$ planets and $n-1$ bidirectional space lanes. These lanes connect all $n$ planets of Country L.

Little P manages a logistics company. The company has several transport plans, each of which is of the form: a logistics spaceship needs to fly from planet $u_i$ to planet $v_i$. Naturally, it takes time for a spaceship to travel along a lane. For lane $j$, the time it takes for any spaceship to travel through it is $t_j$, and no interference occurs between any two spaceships.

To encourage scientific innovation, the King of Country L allows Little P's logistics company to participate in the construction of Country L's space lanes, meaning Little P is allowed to build a wormhole on one lane. A spaceship does not consume any time when traveling through a wormhole.

Before the wormhole construction is completed, Little P's logistics company has already scheduled $m$ transport plans. After the wormhole is built, these $m$ transport plans will start simultaneously, and the spaceships will depart together. When all $m$ transport plans are completed, the phased work of Little P's logistics company is finished.

If Little P can freely choose which lane to build a wormhole on, what is the minimum time required for Little P's logistics company to complete its phased work?

Input

The input file is named transport.in. The first line contains two integers $n$ and $m$, representing the number of planets in Country L and the number of transport plans scheduled by Little P's company. The planets are numbered from 1 to $n$. The next $n-1$ lines describe the construction of the lanes. The $i$-th line contains three integers $a_i, b_i$, and $t_i$, indicating that the $i$-th bidirectional lane is built between planet $a_i$ and planet $b_i$, and the time it takes for any spaceship to travel through it is $t_i$. The next $m$ lines describe the transport plans. The $j$-th line contains two integers $u_j$ and $v_j$, indicating that the $j$-th transport plan is to fly from planet $u_j$ to planet $v_j$.

Output

The output file is named transport.out. The output contains 1 line with a single integer, representing the minimum time required for Little P's logistics company to complete its phased work.

Examples

Input 1

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

Output 1

11

Note 1

If a wormhole is built on the 1st lane: the time taken for the three plans is 11, 12, 11 respectively, so the required time is 12. If a wormhole is built on the 2nd lane: the time taken for the three plans is 7, 15, 11 respectively, so the required time is 15. If a wormhole is built on the 3rd lane: the time taken for the three plans is 4, 8, 11 respectively, so the required time is 11. If a wormhole is built on the 4th lane: the time taken for the three plans is 11, 15, 5 respectively, so the required time is 15. If a wormhole is built on the 5th lane: the time taken for the three plans is 11, 10, 6 respectively, so the required time is 11. Building a wormhole on either the 3rd or 5th lane can minimize the time required to complete the phased work, which is 11.

Input 2

(See the files transport/transport2.in in the provided directory)

Output 2

(See the files transport/transport2.ans in the provided directory)

Constraints

The scope and characteristics of all test data are shown in the table below:

For all data: $1 \le a_i, b_i, u_j, v_j \le n$, $0 \le t_i \le 1000$. Please pay attention to the impact of constant factors on program efficiency.