Задача E. Путешествие ≡

Условие

Утенок Даки только выпустился из университета и устроился на работу разработчиком игр. Ему поручили создание новой игры SpaceWar. Игра заключается в сражениях с космическим флотом противника путём отправки флотов кораблей между планетами.

Даки закончил разработку и решил проверить качество игры самостоятельно. В ходе проверки утенок понял, что в игре играет роль не только мощь флота, но и распределение его между планетами, чтобы вражеский флот не смог захватывать территории. Даки решил опробовать новую тактику и, несмотря на опасность потери планет, не разделять свой флот. Так он сможет с легкостью захватывать планеты. Но такая тактика имеет большой недостаток: во время нападения на новые планеты собственные территории беззащитны. Поэтому утенок хочет рассчитывать время, за которое его флот сможет добраться до планеты.

В этой игре между двумя планетами иногда появляются "кротовые норы" (англ. wormholes), пройдя через которые, флот может переместиться вперед во времени и оказаться у следующей планеты. В то же время может также существовать "обычный" путь между планетами, который флот может преодолеть за некоторое время. Существование кротовых нор и обычного пути не связаны между собой. Кротовые норы появляются не сразу и, если флот окажется у планеты, нора около которой еще не образовалась, он не сможет ею воспользоваться. Воспользоваться норой в обратном направлении невозможно. Даки хочет определить, в какой самый ранний момент времени его флот, находящийся у планеты A, может оказаться у планеты B.

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

Первая строка содержит 3 целых числа: N, A, B – количество планет, планету с флотом и планету-цель, соответственно.

Далее следует строка с 2 целыми числами: M – количество кротовых нор и K – количество обычных путей.

Последующие M строк содержат 4 целых числа: A_i, B_i – две планеты, между которыми появляется нора, t_i – время её появления и dt_i – насколько изменится время при перемещении по ней из A_i в B_i.

Далее идут K строк в таком формате: A_j, B_j, t_j – две планеты и время пути между ними.

Считаем, что изначально время равно 0. Все планеты нумеруются от 1 до N включительно. Обычные пути существуют в любое время.

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

Выведите единственное число – самое раннее время в которое флот сможет оказаться у планеты B.

Гарантируется, что путь существует.

Ограничения

1 ≤ A, B, A_i, B_i, A_j, B_j ≤ N ≤ 10⁴

N ≤ M + K ≤ 10⁵

0 ≤ t_i, dt_i, t_j ≤ 10⁹

Примеры тестов

6 3 5
3 6
6 3 0 0
1 3 2 3
2 1 0 1
3 5 3
1 6 2
5 1 4
3 6 0
5 2 1
2 4 2

3

5 3 2
0 8
3 2 4
1 4 1
5 2 2
5 3 5
1 5 3
2 4 1
4 1 3
4 3 2

4

Разбор

Для решения задачи можно воспользоваться модифицированным алгоритмом Дейкстры. Длина пути в данном случае эквивалентна самом раннему времени прибытия.

Напомним, что в этом алгоритме вершины почерёдно помечаются как обработанные, что означает что текущее найденное расстояние до них является кратчайшим.

На этапе релаксации пути помимо рёбер, исходящих из только что помеченной вершины, следует также рассмотреть новые рёбра, образовавшиеся при появлении "кротовых нор". При этом в качество новой длины пути следует брать сумму времени перемещения по норе и минимума из времени прибытия в помеченной вершину и времени появления норы.

Для повышения эффективности выбора помечаемой вершины можно использовать бинарную кучу.