Задача 5. Парад

[mka91x]

Имя входного файла: standard input
Имя выходного файла: standard output
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 MiB

В городе Энск усиленно готовятся к проведению праздничных мероприятий по случаю
очередного Дня Победы и перекрывают улицы (естественно, строго по графику!) для репетиции парада. Однако даже в праздничное время люди могут внезапно заболеть, поэтому
необходимо знать, за какое минимальное время от момента вызова скорая помощь сможет
добраться от места A до места B .
План города представлен в виде взвешенного ориентированного графа с дугами – улицами. Вес дуги – длина проезжей части улицы в километрах. Если улица имеет не одностороннее движение, то ей соответствуют 2 дуги, веса которых могут быть различны.
Скорая помощь едет с постоянной скоростью 1 км/мин. Скорая не должна быть на улице
в то время, когда та перекрыта, но может останавливаться как на открытой улице, так и
в вершинах графа, если это необходимо. Скорая может начать движение в любой момент
после ее вызова. Места A и B являются вершинами графа.

Формат входных данных

В первой строке пять целых чисел: N, 2 ⩽ N < 10^5 – число вершин графа, M,
1 ⩽ M ⩽ min(N · (N − 1), 3 · 10^5) – число дуг, R, 0 ⩽ R < 10^5 – число перекрытий улиц,
A – номер начальной вершины, B – номер конечной вершины (вершины нумеруются с нуля).
Далее M строк по 3 целых числа, которые описывают дугу графа: начальная вершина,
конечная вершина и вес w, 1 ⩽ w ⩽ 10000.
Далее в R строках по 4 целых неотрицательных числа, которые описывают перекрытия
улиц: номер начальной вершины и номер конечной вершины дуги графа, соответствующей
перекрываемой улице, время начала перекрытия и время окончания перекрытия в минутах
(не более 10^9, время окончания всегда больше времени начала) относительно момента вызова
скорой. Обращаем внимание, что улицы могут перекрываться не один раз! Гарантируется,
что интервалы перекрытий не совпадают и что для каждого заданного перекрытия дуга
графа существует.

Формат выходных данных

В единственной строке целое число – кратчайшее время в минутах от момента вызова
скорой, за которое она доедет из A в B.