P3597 [POI 2015 R3] Trips

Given a weighted directed graph with $n$ vertices and $m$ edges, where each edge weight is one of $1$, $2$, or $3$. Sort all possible paths by their total length and output the length of the $k$-th shortest path. Note that a path does not have to be simple; the same vertex may be visited multiple times.

The first line contains three integers $n, m, k$ ($1 \le n \le 40$, $1 \le m \le 1000$, $1 \le k \le 10^{18}$). Each of the next $m$ lines contains three integers $u, v, c$ ($1 \le u, v \le n$, $u \ne v$, $1 \le c \le 3$), indicating there is a directed edge from $u$ to $v$ with length $c$. **Parallel edges may exist.**

Output a single positive integer: the length of the $k$-th shortest path. If it does not exist, output $-1$.

Sample explanation: Paths of length $1$: $1\to 2$, $5\to 3$, $4\to 5$. Paths of length $2$: $2\to 3$, $3\to 4$, $4\to 5\to 3$. Paths of length $3$: $4\to 6$, $1\to 2\to 3$, $3\to 4\to 5$, $5\to 3\to 4$. Paths of length $4$: $5\to 3\to 4\to 5$. ---- Original title: Wycieczki. Translated by ChatGPT 5