P17130 [ICPC 2025 Shanghai R] Yet another mailbox problem

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

Yana、Mino、White 和 Huzz 是最好的朋友。 一天，教练让 White、Mino 和 Huzz 准备一场模拟赛。Huzz 设计了一道漂亮的搜索题，其复杂度关于 $k$ 是指数级的。他仔细检查了整道题目的描述，唯独漏掉了一个细节：他误将 $k \le 10$ 写成了 $k \le 5 \times 10^5$。后来，这道题出现在了一场模拟赛中。愤怒的参赛者 Yana 找到 Huzz，质问这道题到底该怎么解。然而 Huzz 似乎忘记了什么，他给出的题目描述看起来略有不同—— 给定一张有 $n$ 个顶点和 $m$ 条边的**有向**图，每条边 $e$ 带有一个介于 $1$ 到 $8$ 之间的整数权重 $w(e)$。 一条路径是一个边的序列 $(e_1, e_2, \cdots, e_\ell)$，使得对于所有 $1 \le i < \ell$，$e_i$ 的终点是 $e_{i+1}$ 的起点。路径的**长度**为 $\ell$，即包含的边数。注意，一条路径可以**多次**包含同一条边。 路径的权重序列为边的权重构成的序列 $[w(e_1), w(e_2), \cdots, w(e_\ell)]$。路径之间按权重序列的**字典序**进行比较。 只要两条路径使用了不同的边，即使它们经过的顶点序列和权重序列完全相同，它们也被视为不同的路径。例如，如果路径 $(e_1, e_2)$ 和 $(e_3, e_4)$ 的权重序列都是 $[1, 2]$，且都沿着顶点 $1 \to 2 \to 3$ 走，只要 $e_1 \ne e_3$ 或 $e_2 \ne e_4$，它们就是不同的。 White 希望找到字典序最小的 $k$ 条路径。由于输出总量可能过大，你只需要输出每条路径的长度。

第一行包含 $3$ 个整数 $n, m, k$ ($2 \le n \le 5 \times 10^5$, $1 \le m \le 5 \times 10^5$, $1 \le k \le 5 \times 10^5$)，分别表示顶点数、边数以及需要求出的路径数。 接下来的 $m$ 行，每行包含 $3$ 个整数 $x, y, z$ ($1 \le x, y \le n$, $1 \le z \le 8$, $x \ne y$)，表示一条有向边 $e = (x, y)$，其权重为 $w(e) = z$。给定的边集中可能包含**重边**。

输出 $k$ 行。第 $i$ 行应包含一个整数，表示权重序列字典序第 $i$ 小的路径的长度。如果这样的路径不足 $i$ 条，则输出 $-1$。

为简便起见，用 $e_j$ 表示输入中的第 $j$ 条边。 对于第一组测试用例，字典序最小的 $8$ 条路径为： - 路径 $(e_1)$，权重序列 $[1]$。 - 路径 $(e_3)$，权重序列 $[1]$。 - 路径 $(e_5)$，权重序列 $[1]$。 - 路径 $(e_5, e_1)$，权重序列 $[1, 1]$。 - 路径 $(e_5, e_1, e_4)$，权重序列 $[1, 1, 2]$。 - 路径 $(e_5, e_1, e_4, e_5)$，权重序列 $[1, 1, 2, 1]$。 - 路径 $(e_5, e_1, e_4, e_5, e_1)$，权重序列 $[1, 1, 2, 1, 1]$。 - 路径 $(e_5, e_1, e_4, e_5, e_1, e_4)$，权重序列 $[1, 1, 2, 1, 1, 2]$。 翻译由 DeepSeek V4 Pro 完成