题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Wycieczki

Bajtazar 迷上了自行车旅行的魅力，计划在字节城的 $k$ 天假期中，每天骑行一条不同的路线，挑战自我。他希望逐渐增加难度，每天的路线不短于前一天。具体来说，第 $i$ 天他想选择字节城中第 $i$ 短的可能路线。请你帮助 Bajtazar 计算第 $k$ 天旅行的路线长度。

字节城有 $n$ 座城市，编号 $1$ 到 $n$，通过单向道路连接，道路长度为 $1$、$2$ 或 $3$ 公里，可能经过隧道或高架桥。旅行路线可在任意城市起止，可多次经过同一城市或道路。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n \leq 40, 1 \leq m \leq 1000, 1 \leq k \leq 10^{18})$，分别表示城市数、道路数和假期天数。

接下来的 $m$ 行描述道路，每行包含三个整数 $u, v, c$ $(1 \leq u, v \leq n, u \neq v, 1 \leq c \leq 3)$，表示从 $u$ 号城市到 $v$ 号城市的单向道路，长度 $c$ 公里。两城市间可能有多条道路。

输出格式

输出一行，一个整数，表示第 $k$ 短旅行的长度。若可行旅行少于 $k$ 条（Bajtazar 需提前结束假期），输出 $-1$。

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

4

• 长度 $1$ 的旅行：$1 \rightarrow 2$，$5 \rightarrow 3$，$4 \rightarrow 5$。
• 长度 $2$ 的旅行：$2 \rightarrow 3$，$3 \rightarrow 4$，$4 \rightarrow 5 \rightarrow 3$。
• 长度 $3$ 的旅行：$4 \rightarrow 6$，$1 \rightarrow 2 \rightarrow 3$，$3 \rightarrow 4 \rightarrow 5$，$5 \rightarrow 3 \rightarrow 4$。
  第 $11$ 短旅行（长度 $4$）例如为：$5 \rightarrow 3 \rightarrow 4 \rightarrow 5$。

附加样例

1. $n=10, k=46$，道路长度随机，形成链状网络，仅有 $45$ 条可行旅行，答案为 $-1$；
2. $n=15, k=10^{12}$，每对城市间有长度 $3$ 的道路。

数据范围与提示

对于 $25\%$ 的数据，$k \leq 1000000$。
对于 $50\%$ 的数据，每条道路 $c=1$。
对于 $75\%$ 的数据，$n \leq 15, m \leq 200, k \leq 10^{12}$。