Найдите кратчайший путь 1
Вам дана карта, состоящая из
n городов и m двунаправленных дорог, соединяющих эти города. Каждая дорога имеет неотрицательную целочисленную длину, обозначенную как . Ваша задача — определить длину кратчайшего пути между городом 1 и городом n.Входные данные
Первая строка содержит два целых числа,
n и m (), которые задают количество городов и количество дорог соответственно.Следующие
m строк содержат по три целых числа , и , разделённых пробелами, которые описывают дорогу между городами и с длиной ().Выходные данные
Программа должна вывести длину кратчайшего пути от города
1 до города n.Примеры
Входные данные | Выходные данные |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB