P14618 [2019 KAIST RUN Fall] 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 $\textbf{unique}$ color $c_i$. A $\textit{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 $\textit{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 $j$ ($1 \le j \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 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 $\texttt{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 $\texttt{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$.