Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и 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
|