ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. All Roads Lead to Snowdrift

Time limit: 2.0 second
Memory limit: 64 MB
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.

Input

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, bin; 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 ≤ pim; 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

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

Sample

inputoutput
4 3
1 2 10
2 3 10
3 4 10
1
2 10 15
38

Notes

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
To submit the solution for this problem go to the Problem set: 2093. All Roads Lead to Snowdrift