21638_SeeYouinYouTube

Ling and Janice are good friends since childhood. Despite their deep friendship, they are eager to compete with each other in every aspect, from study to sports, from divination to having dreams. Some day, they fall in love with the same boy and get involved in a fierce (also boring team game against each other.

On the first few rounds, Ling's team takes a 3 to 1 lead. This night, both teams come to a cemetery and start a new round, to distribute pies to ghost. Janice realizes she must win this round, or she will be beaten by Ling. There are N tombs in the cemetery, which are numbered from 1 to N. Both teams are at tomb 1. There are some tunnels connecting pairs of tombs, allowing one to climb from one end to the other. Each team should go to every tomb to leave some pies.

It's risky to climb in the tunnel, so Janice wants to minimize the total length of the tunnels which they will go through. Unfortunately, Ling is well trained for Chinese Qigong, and she has the amazing capability to shorten one tunnel at a time. Janice is confused after that. So she turns to you, a member of her team, to let her know the minimum total length every time something is changed.

There are multiple test cases. Each case start with a line containing two positive integers, N ( N ≤ 10⁴ ) and T ( T ≤ 10⁵ ), indicating the number of tombs and number of tunnels. T lines followed, each contains three numbers u_i, v_i and l_i, indicating that there is a tunnel of length l_i connecting tomb u_i and v_i ( 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, l_i > 0 ). The next line contains one positive integer Q ( Q ≤ 10⁴ ). Then Q hues followed, each containing two positive numbers a_i, w_i ( 1 ≤ a_i ≤ T, w_i > 0 ), means that the length of the a_i-th tunnel in the input become w_i, where w_i will be strictly less then the tunnel's current length. The test data guarantees that all the tombs can be reached from tomb number 1. No two tunnels connect same pair of tombs. The total length of all the tunnels fits in a 32-bit unsigned integer. Input is terminated by N=0 and T=0.

For each test case, first output a line containing the minimum total length of the tunnels to be use. Then for each time Ling using her Qigong, output a line to update the value. Output one empty line after each test case.

2 1
1 2 3
1
1 1
5 6
1 2 5
2 3 3
1 4 11
2 4 6
3 5 9
4 5 12
3
3 3
2 1
6 8
0 0

3
1

23
20
18
17