Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Для Фёдора сегодняшний вечер особенный — впервые за много лет в Екатеринбурге даёт свой концерт легендарная немецкая рок-группа Decline. И, как назло, именно в этот вечер повалил снег, основательно замедлив движение по всем дорогам. А ехать до концертного зала Фёдору нужно через весь город. Немного спасает ситуацию снегоуборочная техника, после проезда которой движение по дорогам заметно оживляется. Правда, во время уборки дороги проезд по ней закрывают.

В нормальную погоду i-ю дорогу можно проехать за время t_i. В снегопад время проезда по ней зависит от количества снега на ней. Если выехать на i-ю дорогу через время T после окончания последней её уборки (или после начала снегопада, если эту дорогу ещё не убирали), то время проезда по ней равняется min(⌈(1 + T/100) · t_i⌉, 100500 · t_i) (⌈x⌉ — округление числа x вверх).

Фёдору удалось найти в интернете полный план уборки дорог. Он хочет выстроить свой маршрут так, чтобы никогда не заезжать на дорогу во время её уборки и успевать съехать с неё до начала следующей уборки. Фёдор может ждать на перекрёстках момента, когда он сможет проехать. Теперь ему нужно выбрать маршрут, при котором он попадёт на концерт как можно раньше, чтобы успеть занять места в первых рядах толпы фанатов.

В первой строке даны целые числа n и m — количество перекрёстков и дорог между ними соответственно (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). Дом Фёдора находится на первом перекрёстке, а концертный зал — на n-м. В i-й из следующих m строк описана i-я дорога в виде целых чисел a_i, b_i и t_i — номеров перекрёстков, которые она соединяет, и времени проезда по ней в нормальную погоду (1 ≤ a_i, b_i ≤ n; 1 ≤ t_i ≤ 10⁶). Все дороги в Екатеринбурге двусторонние, между любыми двумя перекрёстками есть не более одной дороги, никакая дорога не соединяет перекрёсток сам с собой. По дорогам можно доехать от дома Фёдора до концертного зала.

В следующей строке записано целое число k (1 ≤ k ≤ 10⁵). Следующие k строк содержат план уборки дорог. В i-й из них записаны целые числа p_i, s_i и f_i — номер дороги и время начала и окончания её уборки (1 ≤ p_i ≤ m; 0 ≤ s_i < f_i ≤ 10⁹). За вечер одну и ту же дорогу могут убирать несколько раз, но одну её уборку всегда заканчивают строго раньше, чем начинают следующую.

Фёдор выезжает из дома в момент начала снегопада. Все времена измеряются в минутах и отсчитываются от времени начала снегопада.

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

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