背景

试题来自 清华大学学生算法协会。

题目描述

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$。

5 5 8
2 1 1
3 1 2
4 1 1
1 5 2
5 2 1

1
1
1
2
3
4
5
6

3 4 10
1 2 1
1 2 1
2 3 2
2 3 3

1
1
2
2
2
2
1
1
-1
-1

6 5 15
1 2 3
2 3 5
3 4 2
3 5 1
5 6 4

1
2
1
1
2
3
4
3
1
1
2
3
2
-1
-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 完成