Trips

Byteasar has recently discovered the joy of bicycle trips. He plans to spend his $k$ days of vacation cycling through the countryside of Byteotia. Each day he wants to take a trip along a different route. He also wants the trips to get harder over time, so each trip must be no shorter than the one before it. Specifically, on day $i$ he follows the $i$-th shortest possible route that passes through the towns of Byteotia. Find the length of the last trip, which he takes on day $k$.

The first line contains three integers $n$, $m$, and $k$ separated by single spaces, where $1 \le n \le 40$, $1 \le m \le 1000$, and $1 \le k \le 10^{18}$. The next $m$ lines describe the roads, one per line. Each line contains three integers $u$, $v$, and $c$ separated by single spaces, where $1 \le u, v \le n$, $u \ne v$, and $1 \le c \le 3$. This means there is a one-way road from town $u$ to town $v$ with length $c$ kilometers. Multiple roads may connect the same pair of towns. Routes may start and end in any towns, and they may pass through the same town or road more than once.

In tests worth 75% of the total score, $n \le 15$, $m \le 200$, and $k \le 10^{12}$. In a subset worth 50% of the total score, $c = 1$ for every road. In a subset of that worth 25% of the total score, $k \le 1\,000\,000$.

Print the length of the $k$-th shortest route on a single line. If there are fewer than $k$ different routes, print $-1$.

Routes of length 1: 1 → 2, 5 → 3, 4 → 5.

Routes of length 2: 2 → 3, 3 → 4, 4 → 5 → 3.

Routes of length 3: 4 → 6, 1 → 2 → 3, 3 → 4 → 5, 5 → 3 → 4.

One possible eleventh shortest route (of length 4) is 5 → 3 → 4 → 5.