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

Автор:Бадерик М.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ A, B, Ai, Bi, Aj, Bj ≤ N ≤ 104

N ≤ M + K ≤ 105

0 ≤ ti, dti, tj ≤ 109

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

Стандартный вход Стандартный выход
1
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
2
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

0.074s 0.009s 13