The first line of input contains the number of test cases T. The descriptions of the test cases
The first line of each test case contains integers n and m (1≤ n≤ 1000; 0≤ rn≤ 100 000) -
the number of cities in the country, and of possible direct connections, respectively.
Each of the following m lines contains three integers x,y,w (1 < x≠ y < n; I≤ w≤
1000 000), denoting that the cities x and y can be connected by a bidirectional highway at cost
w. There might be many ways to connect a single pair of cities.
The following line contains an integer q (1《 q < 1 000 000) - the number of rulings of the
committees. Each of the following q lines contains two integers. The first of the lines contains
the initial rulings 21, hi, given directly. The rest of the rulings are encoded. The numbers in the
j-th of the lines for j > I are lj + Cj_i and hj + cj_i, where lj and hj are the actual rulings and
cj-l is the correct answer for the preceding rulings /j_i and hj_i.
All rulings satisfv I≤ tj≤ hj < 1000 000.