Byteasar 最近发现了自行车旅行的乐趣。因此，他打算在 Byteotia 风景优美的乡村度过 $k$ 天的假期。他希望每天都选择一条不同的路线进行骑行。此外，他希望通过要求每一天的路线长度都不短于前一天，来逐渐增加旅行的难度。具体来说：在第 $i$ 天，Byteasar 想要走第 $i$ 短的可能路线。请帮助 Byteasar 确定他假期最后一天（即第 $k$ 天）所走路线的长度。

Byteotia 有 $n$ 个城镇，编号从 $1$ 到 $n$。城镇之间由单向道路连接，每条道路的长度为 $1$、$2$ 或 $3$ 公里。这些道路可能穿过隧道或高架桥。我们考虑所有在 Byteotia 任意城镇之间开始和结束的路线，并允许路线多次经过同一个城镇或道路。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le n \le 40, 1 \le m \le 1000, 1 \le k \le 10^{18}$)，分别表示城镇数量、道路数量和假期天数。接下来的 $m$ 行描述了道路，每行包含三个整数 $u$、$v$ 和 $c$ ($1 \le u, v \le n, u \neq v, 1 \le c \le 3$)，表示有一条从城镇 $u$ 到城镇 $v$ 的长度为 $c$ 公里的单向道路。两个城镇之间可能存在多条道路。

在总分 $75\%$ 的测试点中，满足 $n \le 15, m \le 200, k \le 10^{12}$。此外，在其中 $50\%$ 的测试点中，每条道路的长度 $c = 1$。最后，在上述 $50\%$ 测试点中的 $25\%$ 中，额外满足 $k \le 1\,000\,000$。

输出格式

输出一行，包含第 $k$ 短路线的长度。如果总的路线数量少于 $k$ 条（在这种情况下，失望的 Byteasar 将缩短他的假期），则输出 $-1$。

样例

输入 1

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

输出 1

4

说明

长度为 $1$ 的路线：$1 \to 2, 5 \to 3, 4 \to 5$。 长度为 $2$ 的路线：$2 \to 3, 3 \to 4, 4 \to 5 \to 3$。 长度为 $3$ 的路线：$4 \to 6, 1 \to 2 \to 3, 3 \to 4 \to 5, 5 \to 3 \to 4$。 第 $11$ 短的路线（长度为 $4$）的一种可能是：$5 \to 3 \to 4 \to 5$。