Петя очень любит волейбол. Однажды он опаздывал на волейбольный матч. Свою собственную машину Петя еще не купил, поэтому ему пришлось ехать на такси. В городе n перекрестков, некоторые из которых соединены двусторонними дорогами. Длина каждой дороги выражается некоторым натуральным числом метров, дороги могут иметь разные длины.
Изначально на каждом перекрестке стоит ровно одно такси. Таксист с i-го перекрестка согласен проехать (возможно, через несколько других перекрестков) не более ti метров и остановиться на каком-то другом перекрестке. Причем цена поездки не зависит от расстояния и равна ci бурлей. Посреди дороги такси останавливаться не могут. Каждое такси можно использовать не более 1 раза. В такси можно сесть только в перекрестке, где оно изначально расположено.
Сейчас Петя находится на перекрестке x, а волейбольный стадион — на перекрестке y. Определите, какая минимальная сумма денег потребуется Пете чтобы доехать до стадиона.
Выходные данные
Если Петя не может доехать на такси, выведите «-1» (без кавычек). Иначе выведите минимальную стоимость поездки.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
Оптимальный путь - поехать из перекрестка 1 к 2 (через 4), потом из 2 в 3. На это потратится 7+2=9 бурлей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7
|
9
|