C. Самолетом, пароходом...
Задачу добавил: alef
Успешно сдано решений: 7
Ограничения по времени: 2 с на тестОграничения по памяти: 256 Мб
Собирается Феофан в путь-дорогу дальнюю, в тридевятое государство. Не одну границу ему придется пересечь, не одну пересадку сделать. Волнуются царь Серапион и царица Пелагея, и потому обратились в транспортно-туристическую компанию "Доставляем!": у нее есть представительства во всех государствах, которые предстоит миновать Феофану.
Сообщение между государствами обеспечивается с помощью M видов транспорта (водный, воздушный, железнодорожный и т.д. — каждому виду транспорта сопоставлен номер от 1 до M). Таким образом, для каждой пары государств существует от 0 до M путей, предназначенных для различных видов транспорта. Будем считать, что двунадесятое государство, из которого отправляется Феофан, имеет номер 1, а тридевятое государство, куда он должен прибыть, имеет номер N.
Царица Пелагея настояла на том, что количество изменений вида транспорта в поездке должно быть минимальным. Не налегке Феофан едет, багажа много, при разгрузке, загрузке да перевозке того гляди потеряют или повредят чего.
Ваша задача — определить наименьшее число изменений вида транспорта в поездке, а также маршрут, по которому Феофан будет следовать. Если существует несколько вариантов маршрута, выведите любой.
Гарантируется, что из любого государства можно добраться в любое другое государство.
Примечание. Обратите внимание, что нет необходимости отыскивать кратчайший из возможных путей.
В первой строке содержится число государств, количество видов транспорта и маршрутов между государствами N, M, K соответственно (3 ≤ N ≤ 105, 2 ≤ M ≤ 105, 2 ≤ K ≤ 105).
Далее в каждой из следующих K строк содержится по три целых числа через пробел, описывающих путь между парой государств. При этом сначала указываются номера государств, а затем вид транспорта, соответствующий этому маршруту.
В первой строке выведите количество государств (включая 1 и N), которые образуют наилучший маршрут, и количество замен видов транспорта, которые произойдут на этом маршруте.
Во второй строке выведите собственно маршрут, составленный из элементов вида 
номер государства
:вид транспорта, где вид транспорта — номер вида транспорта, которым нужно выезжать из этого государства.
Каждую пару выводите через пробел. Выводить город N в маршруте не нужно.
Входные данные
5 3 5
1 2 1
2 3 2
3 5 3
1 4 1
4 5 2
3 1
1:1 4:2
Входные данные
5 2 5
1 2 2
2 3 2
3 5 2
1 4 1
4 5 2
4 0
1:2 2:2 3:2
Входные данные
5 2 6
1 2 2
2 3 2
3 4 2
4 5 2
1 3 1
3 5 2
4 0
1:2 2:2 3:2