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 ti.
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) · ti⌉, 100500 · ti) (⌈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 ≤ 105; 1 ≤ m ≤ 105). 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 ai, bi and ti meaning the
numbers of crossroads connected by it, and travel time through it in
normal weather conditions (1 ≤ ai, bi ≤ n; 1
≤ ti ≤ 106). 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 ≤ 105).
The following k lines contain the plan of roads cleaning. The i-th
one contains integers pi, si and fi that are the road number and
moments when the cleaning will be started and finished (1 ≤ pi
≤ m; 0 ≤ si < fi ≤ 109). 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
1 2 10
2 3 10
3 4 10
2 10 15
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).
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Personal Contest 2014