Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.
Входные данные
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1<=N<=100000, 0<=K<=300000), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с двусторонним движением – три целых числа ai, bi и li (1aibiN, 1li106). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi. В последней строке находятся два числа А и В – номера городов, между которыми надо посчитать кратчайшее расстояние (1<=A,B<=N )
Выходные данные
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города А до города В доехать невозможно, выведите –1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1 |
115 |