The first line of input contains the number of test cases T. The descriptions of the test cases

follow:

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.