ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2093. Все дороги ведут в сугроб

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Для Фёдора сегодняшний вечер особенный — впервые за много лет в Екатеринбурге даёт свой концерт легендарная немецкая рок-группа Decline. И, как назло, именно в этот вечер повалил снег, основательно замедлив движение по всем дорогам. А ехать до концертного зала Фёдору нужно через весь город. Немного спасает ситуацию снегоуборочная техника, после проезда которой движение по дорогам заметно оживляется. Правда, во время уборки дороги проезд по ней закрывают.
В нормальную погоду i-ю дорогу можно проехать за время ti. В снегопад время проезда по ней зависит от количества снега на ней. Если выехать на i-ю дорогу через время T после окончания последней её уборки (или после начала снегопада, если эту дорогу ещё не убирали), то время проезда по ней равняется min(⌈(1 + T/100) · ti⌉, 100500 · ti) (⌈x⌉ — округление числа x вверх).
Фёдору удалось найти в интернете полный план уборки дорог. Он хочет выстроить свой маршрут так, чтобы никогда не заезжать на дорогу во время её уборки и успевать съехать с неё до начала следующей уборки. Фёдор может ждать на перекрёстках момента, когда он сможет проехать. Теперь ему нужно выбрать маршрут, при котором он попадёт на концерт как можно раньше, чтобы успеть занять места в первых рядах толпы фанатов.

Исходные данные

В первой строке даны целые числа n и m — количество перекрёстков и дорог между ними соответственно (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). Дом Фёдора находится на первом перекрёстке, а концертный зал — на n-м. В i-й из следующих m строк описана i-я дорога в виде целых чисел ai, bi и ti — номеров перекрёстков, которые она соединяет, и времени проезда по ней в нормальную погоду (1 ≤ ai, bin; 1 ≤ ti ≤ 106). Все дороги в Екатеринбурге двусторонние, между любыми двумя перекрёстками есть не более одной дороги, никакая дорога не соединяет перекрёсток сам с собой. По дорогам можно доехать от дома Фёдора до концертного зала.
В следующей строке записано целое число k (1 ≤ k ≤ 105). Следующие k строк содержат план уборки дорог. В i-й из них записаны целые числа pi, si и fi — номер дороги и время начала и окончания её уборки (1 ≤ pim; 0 ≤ si < fi ≤ 109). За вечер одну и ту же дорогу могут убирать несколько раз, но одну её уборку всегда заканчивают строго раньше, чем начинают следующую.
Фёдор выезжает из дома в момент начала снегопада. Все времена измеряются в минутах и отсчитываются от времени начала снегопада.

Результат

Выведите единственное целое число — минимальное время, за которое Фёдор сможет доехать до концертного зала.

Пример

исходные данныерезультат
4 3
1 2 10
2 3 10
3 4 10
1
2 10 15
38

Замечания

В примере Фёдор проезжает по первой дороге за 10 минут, затем ждёт 5 минут на втором перекрёстке, пока закончат убирать вторую дорогу, после чего проезжает эту дорогу также за 10 минут. Через 25 минут после старта он выезжает на третью дорогу, которую проезжает за 13 минут (из-за снега, выпавшего на неё за 25 минут снегопада).
Автор задачи: Денис Дублённых
Источник задачи: Открытое личное первенство УрФУ по программированию 2014