P17130 [ICPC 2025 Shanghai R] Yet another mailbox problem

Yana, Mino, White, and Huzz are best friends. One day, the coach asked White, Mino, and Huzz to prepare a mock contest. Huzz designed a beautifully search problem whose complexity is exponential with respect to $k$. He carefully checked the entire problem statement, except for one detail: he accidentally wrote $k \le 5 \times 10^5$ instead of $k \le 10$. Later, this problem appeared in a mock contest. The furious contestant, Yana, came to Huzz, asking how the problem was supposed to be solved. But he seemed to have forgotten something, and the problem statement he provided looked slightly different — You are given a **directed** graph with $n$ vertices and $m$ edges, where each edge $e$ is assigned an integer weight $w(e)$ between $1$ and $8$. A path is a sequence of edges $(e_1, e_2, \cdots, e_\ell)$ such that the endpoint of $e_i$ is the startpoint of $e_{i+1}$ for all $1 \le i < \ell$. The length of the path is $\ell$, the number of edges it contains. Note that a path may contain the same edge **multiple times**. The weight sequence of the path is the sequence of edge weights $[w(e_1), w(e_2), \cdots, w(e_\ell)]$. Paths are compared by **lexicographical order** of their weight sequences. Two paths are considered distinct as long as they use different edges, even if they share the same vertex sequence and weight sequence. For example, if both paths $(e_1, e_2)$ and $(e_3, e_4)$ have weight sequence $[1, 2]$, and both traverse vertices $1 \to 2 \to 3$, they are still distinct as long as $e_1 \ne e_3$ or $e_2 \ne e_4$. White wants to find the lexicographically smallest $k$ paths. Since the total output may be too large, you only need to output the length of each path.

The $1$st line of the input contains $3$ integers $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$), representing the number of vertices, the number of edges, and the required number of paths. Each of the next $m$ lines contains $3$ integers $x, y, z$ ($1 \le x, y \le n$, $1 \le z \le 8$, $x \ne y$), representing a directed edge $e = (x, y)$ with weight $w(e) = z$. The given edge set may contain **multiple edges**.

Print $k$ lines. The $i$-th line should contain a single integer, the length of the path whose weight is the $i$-th smallest in lexicographical order. If there are fewer than $i$ paths, output $-1$ instead.

For simplicity, let $e_j$ denote the $j$-th input edge. For the first testcase, the lexicographically smallest $8$ paths are: - Path $(e_1)$, weight sequence $[1]$. - Path $(e_3)$, weight sequence $[1]$. - Path $(e_5)$, weight sequence $[1]$. - Path $(e_5, e_1)$, weight sequence $[1, 1]$. - Path $(e_5, e_1, e_4)$, weight sequence $[1, 1, 2]$. - Path $(e_5, e_1, e_4, e_5)$, weight sequence $[1, 1, 2, 1]$. - Path $(e_5, e_1, e_4, e_5, e_1)$, weight sequence $[1, 1, 2, 1, 1]$. - Path $(e_5, e_1, e_4, e_5, e_1, e_4)$, weight sequence $[1, 1, 2, 1, 1, 2]$.