17514번 - Lexicographically Minimum Walk 다국어

문제

There is a directed graph $G$ with $N$ nodes and $M$ edges. Each node is numbered 1ドル$ through $N,ドル and each edge is numbered 1ドル$ through $M$. For each $i$ (1ドル \le i \le M$), edge $i$ goes from vertex $u_i$ to vertex $v_i$ and has a unique color $c_i$.

A walk is defined as a sequence of edges $e_1,ドル $e_2,ドル $\cdots,ドル $e_{l}$ where for each 1ドル \le k < l,ドル $v_{e_k}$ (the tail of edge $e_k$) is the same as $u_{e_{k+1}}$ (the head of edge $e_{k+1}$). We can say a walk $e_1,\ e_2,\ \cdots,\ e_l$ starts at vertex $u_{e_1}$ and ends at vertex $v_{e_l}$. Note that the same edge can appear multiple times in a walk.

The color sequence of a walk $e_1,\ e_2,\ \cdots,\ e_l$ is defined as $c_{e_1},\ c_{e_2},\ \cdots,\ c_{e_l}$.

Consider all color sequences of walks of length at most 10ドル^{100}$ from vertex $S$ to vertex $T$ in $G$. Write a program that finds the lexicographically minimum sequence among them.

입력

The first line of the input contains four space-separated integers $N,ドル $M,ドル $S,ドル and $T$ (1ドル \le N \le 100,000円,ドル 0ドル \le M \le 300,000円,ドル 1ドル \le S \le N,ドル 1ドル \le T \le N,ドル $S \neq T$).

Then $M$ lines follow: the $i$ (1ドル \le i \le M$)-th of them contains three space-separated integers $u_i,ドル $v_i$ and $c_i$ (1ドル \le u_i, v_i \le N,ドル $u_i \neq v_i,ドル 1ドル \le c_i \le 10^{9}$); it describes a directional edge from vertex $u_i$ to vertex $v_i$ with color $c_i$.

The graph doesn't have multiple edges or loops, and each edge has a unique color. Formally, for any 1ドル \le i < j \le M,ドル $c_i \neq c_j$ and $(u_i,\ v_i) \neq (u_j,\ v_j)$ holds.

출력

If there is no walk from vertex $S$ to vertex $T,ドル print "IMPOSSIBLE". (without quotes)

Otherwise, let's say $a_1,\ a_2,\ \cdots,\ a_l$ is the lexicographically minimum sequence among all color sequences of length at most 10ドル^{100}$ from vertex $S$ to vertex $T$.

• If $l \le 10^{6},ドル print $a_1,\ a_2,\ \cdots,\ a_l$ in the first line. There should be a space between each printed integer.
• If $l > 10^{6},ドル print "TOO LONG". (without quotes)

제한

노트

Sequence $p_1, p_2, \cdots, p_{n}$ is lexicographically smaller than another sequence $q_1, q_2, \cdots, q_{m}$ if and only if one of the following holds:

• There exists a unique $j$ (0ドル \le j < \min(n, m)$) where $p_1 = q_1,ドル $p_2 = q_2,ドル $\cdots,ドル $p_{j} = q_{j}$ and $p_{j+1} < q_{j+1}$.
• $n < m$ and $p_1 = q_1,ドル $p_2 = q_2,ドル $\cdots,ドル $p_n = q_n$. In other words, $p$ is a strict prefix of $q$.