Задача D. Космическая доставка ≡

Условие

Утенок Даки решил открыть свою доставку товаров в родной галактике. Для успешного запуска бизнеса необходимо привлечь клиентов. Поэтому утенок решил сделать упор на скидки и качество услуг.

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

Галактика утенка имеет множество планет, между которыми существуют специальный космические дороги, позволяющие перемещаться по ним в обе стороны. Как и по дорогам на планетах, в космосе преодоление дороги занимает некоторое время. Но помимо обычных дорог, в галактике время от времени появляются “кротовые норы” (англ. wormholes), каждая нора имеет свое сопротивление, поэтому для её преодоления необходимо затратить какое-то время, но их особенность заключается в том, что они позволяют переместиться минуя космические дороги. Норы существуют очень долго, поэтому считается, что они почти вечные.

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

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

Первая строка содержит 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

Ограничения

2 ≤ N ≤ 10⁴

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

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 7
3 2 4
1 4 1
5 2 2
5 3 5
1 5 3
2 4 1
4 3 2

3