题目描述

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$。

附加样例

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

数据范围与提示

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