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