30. Путь в ближайший

Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти длину пути и путь между двумя самыми ближайшими, не соседними городами .

Входные данные

В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.

Выходные данные

Напечатать номера найденных городов, суммарную длину и путь. Номера вершин напечатать в возрастающем порядке.

Пример

input.txt	output.txt
5 5 1 2 8 1 3 4 2 3 7 3 4 8 4 5 3	3 5 11 3 4 5