Главные дороги

Город, в котором живет Гоша, имеет N перекрестков, некоторые из которых соединены дорогами. По каждой дороге разрешено движение в обоих направлениях. Каждый день Гоша ездит на машине из дома на работу и обратно. Но дороги в городе, где живет Гоша, не очень хорошие, они часто портятся, и приходится их ремонтировать. Гоша заметил, что когда некоторые дороги закрывают на ремонт, часто он все равно может доехать из дома до работы за то же время, что в случае, когда ни одна дорога на ремонт не закрыта. С другой стороны, встречаются дороги такие, что когда они закрываются на ремонт, то время, которое требуется Гоше, чтобы добраться от дома до работы, увеличивается. А иногда Гоша просто не может доехать от дома до работы на машине. Такие дороги Гоша называет главными.

Помогите Гоше найти все главные дороги в городе.

Входные данные
Первая строка входного файла INPUT.TXT содержит N и M – количество перекрестков и дорог в городе, соответственно (2 ≤ N ≤ 20 000, 1 ≤ M ≤ 100 000). Гоша живет около перекрестка 1, а работает у перекрестка N.

Следующие M строк содержат информацию о дорогах. Каждая дорога описывается двумя перекрестками, которые она соединяет, и временем, которое необходимо Гоше, чтобы проехать по этой дороге от одного конца до другого. Время проезда по дороге – натуральное число, не превышающее 100 000. Между парой перекрестков может быть несколько дорог, но никакая дорога не соединяет перекресток с самим собой.

Гарантируется, что если все дороги доступны, Гоша может добраться от дома до работы.

Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите K – количество главных дорог. На второй строке выведите K чисел – номера главных дорог. Дороги пронумерованы от 1 до M в том порядке, в котором они заданы во входном файле.
Пример:
6 7 2
1 2 1 5 7
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2

0

Prositka453, думаете создав дубль темы Главные дороги вы получите что-то новое?
Спешу разочаровать, но нет. Более того, это действо запрещено п.5.5 правил форума.
К слову решение этой задачи у меня есть и, думаю, не у меня одного. Просто жду каких-то действий от вас. Вы справились с алгоритмом кратчайшего пути?

1

Извиняюсь.

0