P14618 [2019 KAIST RUN Fall] Lexicographically Minimum Walk

有一个包含 $N$ 个节点和 $M$ 条边的有向图 $G$。每个节点编号为 $1$ 到 $N$，每条边编号为 $1$ 到 $M$。对于每个 $i$（$1 \le i \le M$），边 $i$ 从顶点 $u_i$ 指向顶点 $v_i$，并且具有 **唯一** 的颜色 $c_i$。 一条 **路径** 定义为边的序列 $e_1, e_2, \cdots, e_{l}$，其中对于每个 $1 \le k < l$，$v_{e_k}$（边 $e_k$ 的终点）与 $u_{e_{k+1}}$（边 $e_{k+1}$ 的起点）相同。我们可以说路径 $e_1, e_2, \cdots, e_l$ 从顶点 $u_{e_1}$ 开始，到顶点 $v_{e_l}$ 结束。注意同一条边可以在一条路径中出现多次。 路径 $e_1, e_2, \cdots, e_l$ 的 **颜色序列** 定义为 $c_{e_1}, c_{e_2}, \cdots, c_{e_l}$。 考虑图 $G$ 中从顶点 $S$ 到顶点 $T$ 的所有长度不超过 $10^{100}$ 的路径的颜色序列。请编写一个程序，找出这些序列中字典序最小的序列。

输入的第一行包含四个以空格分隔的整数 $N$、$M$、$S$ 和 $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$）。 接下来是 $M$ 行：第 $j$（$1 \le j \le M$）行包含三个以空格分隔的整数 $u_i$、$v_i$ 和 $c_i$（$1 \le u_i, v_i \le N$，$u_i \neq v_i$，$1 \le c_i \le 10^{9}$）；它描述了一条从顶点 $u_i$ 指向顶点 $v_i$ 且颜色为 $c_i$ 的有向边。 图中没有重边，且每条边有唯一的颜色。形式化地说，对于任意 $1 \le i < j \le M$，$c_i \neq c_j$ 且 $(u_i, v_i) \neq (u_j, v_j)$ 成立。

如果不存在从顶点 $S$ 到顶点 $T$ 的路径，输出 `IMPOSSIBLE`（不带引号）。 否则，设 $a_1, a_2, \cdots, a_l$ 是从顶点 $S$ 到顶点 $T$ 的所有长度不超过 $10^{100}$ 的路径的颜色序列中字典序最小的序列。 - 如果 $l \le 10^{6}$，在第一行输出 $a_1, a_2, \cdots, a_l$。每个输出的整数之间应有空格。 - 如果 $l > 10^{6}$，输出 `TOO LONG`（不带引号）。

序列 $p_1, p_2, \cdots, p_{n}$ 在字典序上小于另一个序列 $q_1, q_2, \cdots, q_{m}$，当且仅当以下条件之一成立： - 存在唯一的 $j$（$0 \le j < \min(n, m)$）使得 $p_1 = q_1$，$p_2 = q_2$，$\cdots$，$p_{j} = q_{j}$ 且 $p_{j+1} < q_{j+1}$。 - $n < m$ 且 $p_1 = q_1$，$p_2 = q_2$，$\cdots$，$p_n = q_n$。换句话说，$p$ 是 $q$ 的严格前缀。 --- 翻译由 DeepSeek V3 完成