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