| Codeforces Round 287 (Div. 2) |
|---|
| Закончено |
Во все лёгкие — это новая компьютерная игра, о которой мечтает много геймеров. В этой игре есть один уровень, сложный даже для опытного игрока.
Уолтер Вильям, главный персонаж игры, хочет вступить в банду под названием Los Hermanos (Братья). Эта банда держит под контролем всю страну, состоящую из n городов, соединенных m двусторонними дорогами. Никакая дорога не соединяет город с самим собой, и для любых двух городов их соединяет не более одной дороги. Страна связная, иными словами, по дорогам можно из любого города добраться до любого другого.
Не по всем дорогам можно проехать. Некоторым дорогам для полной функциональности необходим ремонт.
Банда собирается ограбить банк! Банк находится в городе 1. Как обычно, самое сложное — это вернуться в свою штаб-квартиру, где полиция их не достанет. Штаб-квартира банды находится в городе n. Чтобы завоевать доверие банды, Уолтер взял операцию на себя и придумал хитроумный план.
Во-первых, путь, по которому надо возвращаться из города 1 в их штаб-квартиру n, должен быть как можно короче, так как очень важно завершить операцию как можно быстрее.
Затем, в качестве подготовки к операции банда должна взорвать все остальные дороги в стране, не лежащие на их пути, чтобы полиция не могла послать подкрепления. Если дорога к моменту операции не работает, взрывать её не нужно, так как по ней и так не проехать.
Если на выбранном пути находится несколько неработающих дорог, их надо отремонтировать перед операцией.
Уолтер обнаружил, что может быть несколько возможных путей минимальной длины, так что он решил выбрать среди них такой путь, который минимизирует общее количество дорог, над которыми банде придётся потрудиться (т. е. взорвать или отремонтировать).
Помогите Уолтеру завершить задание и завоевать доверие банды.
В первой строке входа записано два целых числа n, m (2 ≤ n ≤ 105, 
), количество городов и количество дорог, соответственно.
В следующих m строках даны описания дорог. Каждое описание состоит из трех целых чисел x, y, z (1 ≤ x, y ≤ n, 
), обозначающих, что между городами x и y есть дорога, работающая, если z = 1, или неисправная, если z = 0.
В первой строке выведите единственное целое число k, минимальное возможное количество дорог, над которые банде придётся затронуть.
В следующих k строках выведите по три целых числа, описывающих дорогу, которую придётся затронуть. В каждой строке должно быть записано три целых числа, x, y, z (1 ≤ x, y ≤ n, ), номера городов, соединенных дорогой, и новое состояние дороги. z = 1 означает, что дорогу между городами x и y надо отремонтировать, а z = 0 означает, что дорогу надо взорвать.
Дороги можно выводить в любом порядке. Каждую затронутую дорогу следует вывести ровно один раз. Города, соединяемые дорогой, разрешается выводить в любом порядке. Если вы выводите дорогу, то её исходное состояние должно отличаться от z.
После исполнения вашего плана в стране должны остаться только рёбра, лежащие на одном кратчайшем пути из 1 в n.
Если есть несколько оптимальных вариантов ответа, выведите любой из них.
2 1
1 2 0
1
1 2 1
4 4
1 2 1
1 3 0
2 3 1
3 4 1
3
1 2 0
1 3 1
2 3 0
8 9
1 2 0
8 3 0
2 3 1
1 4 1
8 7 0
1 5 1
4 6 1
5 7 0
6 8 0
3
2 3 0
1 5 0
6 8 1
В первом тесте единственный путь — 1 - 2
Во втором тесте единственный кратчайший путь — 1 - 3 - 4
В третьем тесте есть несколько кратчайших путей, но оптимальный из них — 1 - 4 - 6 - 8
