Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. For Fedor this evening is very special, because for the first time in many years the legendary German rock band Decline gives a concert in Yekaterinburg. Fedor needs to go through the city to the concert hall. And, as ill luck would have it, this day the snow began to fall, thoroughly slowing down the traffic on all roads. A snow-clearing equipment slightly saves the situation, but during the cleaning of the road the driving through it is closed.

In normal weather Fedor can drive through the i-th road in time t_i. In the snowfall, travel time depends on the amount of snow on a road. If Fedor starts his travel through the i-th road after time T after its last cleaning (or after the beginning of a snowfall, if this road has not been cleaned yet), the travel time through it will be equal to min(⌈(1 + T/100) · t_i⌉, 100500 · t_i) (⌈x⌉ is x rounded upwards).

Fedor has found on the Internet a complete plan of roads cleaning. He wants to construct his route without driving through a road during its cleaning (and always leaving a road before its next cleaning). Fedor may be waiting on the crossroads for the moment when he can drive further. He needs to select a route which allows him to get to the concert hall as soon as possible.

The first line contains integers n and m that are the number of crossroads and roads between them respectively (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). Fedor’s house is at the first crossroad, and a concert hall is at the n-th. The i-th of the following m lines describes the i-th road as integers a_i, b_i and t_i meaning the numbers of crossroads connected by it, and travel time through it in normal weather conditions (1 ≤ a_i, b_i ≤ n; 1 ≤ t_i ≤ 10⁶). All roads in Yekaterinburg are bilateral, between any two crossroads there is no more than one road, no road connects a crossroad with itself. It is possible to drive from Fedor’s house to a concert hall by roads.

The next line contains an integer k (1 ≤ k ≤ 10⁵). The following k lines contain the plan of roads cleaning. The i-th one contains integers p_i, s_i and f_i that are the road number and moments when the cleaning will be started and finished (1 ≤ p_i ≤ m; 0 ≤ s_i < f_i ≤ 10⁹). During the evening the same road can be cleaned several times, but one of its cleaning always ends up strictly before the next one begins.

Fedor leaves his house at the beginning of a snowfall. All times are counted from that moment and measured in minutes.

Output the minimum time in which Fedor will be able to get to the concert hall.

In the example, Fedor passes the first road in 10 minutes, then waits 5 minutes at the second crossroad for the end of the cleaning, then passes the second road in 10 minutes. 25 minutes after the start, he goes to the third road and passes it in 13 minutes (because of the snow that had fallen on it during 25 minutes of snowfall).