Description

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.

Input Format

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 Format

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

6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3

4

Hint

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