HELP, the end is approaching! Tak-o is trying to destroy the world. He has built 2 main bases, some middle towers to control specific areas and bridges between towers to send his troops around. Our superhero Birkan has an idea. If we can disconnect the 2 main bases by destroying towers and bridges, we will be able to stop Tak-o. Destroying towers and bridges have a cost. Help Birkan with computing the minimum cost of disconnecting Tak-o's bases to save our world.

• There is only one bridge between two towers, there are also bridges between bases and towers.
• We cannot destroy the bases yet.
• Note that some towers may be isolated and some paths may be dead-ends.

Input

• First line of input contains two integers \(\mathbf{T}\) and \(\mathbf{B}\), representing the number of towers+bases (\(\mathbf{T}\)) and the number of bridges (\(\mathbf{B}\)).
• Following \(\mathbf{T}-2\) lines, one per tower, contain the information below, separated by spaces: An integer \(i\), the identifier of the tower. The first base has id 1 and that the second has id \(\mathbf{T}\). Another integer \(t\), specifying the cost of destroying the tower.
• Then the remaining \(\mathbf{B}\) lines, one per bridge, contain the following information separated by spaces: Two integers \(x\) and \(y\) specifying the identifiers of the towers linked by the bridge. Remember that the bridge is bidirectional. An integer \(z\) specifying the cost of destroying the bridge.
• The last line of the input will be '0 0'.

Output

For each test case, print a line with the minimum cost of interrupting the communication between the two bases. Print 0 if the bases are not connected.

Constraints

• \(2 ≤ \mathbf{T} ≤ 50\)
• \(0 ≤ \mathbf{B} ≤ 1000\)
• \(2 ≤ i ≤ \mathbf{T} − 1\)
• \(0 ≤ t ≤ 100000\)
• \(1 ≤ x < y ≤ \mathbf{T}\)
• \(0 ≤ z ≤ 100000\)

Examples

Input

3 3
2 7
1 2 9
1 3 1
2 3 10
0 0

Output

8

Input

4 4
2 8
3 6
1 2 9
1 3 1
2 4 5
3 4 7
0 0

Output

6

Notes

For the first example, we should destroy the tower with ID:2 and the bridge between base1(tower ID:1) and base2(tower ID:3).