Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Графы

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

05/11/2012 | Тренировка (задачи NEERC 2010) (I) |

*Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

New labyrinth attraction is open in New Lostland amusement park.
The labyrinth consists of `n` rooms connected by `m` passages. Each passage
is colored into some color `c_i`. Visitors of the labyrinth are
dropped from the helicopter to the room number 1 and their goal is to get to
the labyrinth exit located in the room number `n`.

Labyrinth owners are planning to run a contest tomorrow. Several
runners will be dropped to the room number 1. They will run to the room number `n` writing
down colors of passages as they run through them. The contestant
with the shortest sequence of colors is the winner of the contest.
If there are several contestants with the same sequence length,
the one with the *ideal path* is the winner. The path is the ideal path if
its color sequence is the lexicographically smallest among shortest paths.

Andrew is preparing for the contest. He took a helicopter tour above New Lostland
and made a picture of the labyrinth. Your task is to help him find the ideal path
from the room number 1 to the room number `n` that would allow him to win the contest.

A sequence `(a_1,\ a_2,\ …,\ a_k)` is lexicographically
smaller than a sequence `(b_1,\ b_2,\ …,\ b_k)` if there exists `i`
such that `a_i\ <\ b_i`, and `a_j\ =\ b_j` for all `j\ <\ i`.

The first line of the input file contains integers `n` and `m` — the number of rooms
and passages, respectively (`2\ ≤\ n\ ≤\ 100\ 000`, `1\ ≤\ m\ ≤\ 200\ 000`).
The following `m` lines describe passages, each passage is described with
three integer numbers: `a_i`, `b_i`, and `c_i` — the numbers of rooms it connects
and its color (`1\ ≤\ a_i,\ b_i\ ≤\ n`, `1\ ≤\ c_i\ ≤\ 10^9`).
Each passage can be passed in either direction. Two rooms
can be connected with more than one passage, there can be a passage from
a room to itself. It is guaranteed that it is possible to reach the room number `n`
from the room number 1.

The first line of the output file must contain `k` — the length of the shortest
path from the room number 1 to the room number `n`. The second line must contain `k` numbers — the colors of passages in the order they must be passed in the ideal path.

Sample Input

4 6 1 2 1 1 3 2 3 4 3 2 3 1 2 4 4 3 1 1

Sample Output

2 1 3