Задача 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