Олимпиадный тренинг

Задача . Кратчайший путь (AB)


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



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6416
Комментарий учителя