Migrated from Lutece 2609 A*

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在 A* 星系中，有 $n$ 个 A 星和 $m$ 个单向虫洞。A* 星系的空间非常混乱，你只能通过单向虫洞在 A* 星系内移动。一个单向虫洞可以花费一定的时间从虫洞的起点传送到终点。你正在第 $1$ 个 A 星上，而你希望前往第 $n$ 个 A 星。时间并不紧迫，你希望游览更多 A* 星系的风景，但时间还是有限的。折衷考虑后，你希望寻找到花费 $k$ 小的时间的方案，并输出这个花费时间。如果没有这样的方案，请输出 $-1$。

注意：你的方案可以多次经过同一个 A 星（包括第 $n$ 个 A 星）。

一句话题意：给你一个 $n$ 个点 $m$ 条边有向图，找到从 $1$ 号点出发到 $n$ 号点结束的第 $k$ 短的路径长度。

Input

第一行三个整数 $n,m,k$，分别表示 A 星个数，虫洞个数和希望找到的花费时间的从小到大的排名。

接下来 $m$ 行，每行三个整数 $u,v,w$，分别表示一个单向虫洞的起点，终点，花费时间。

Output

一个整数，表示从 $1$ 号 A 星到 $n$ 号 A 星花费 $k$ 小的时间。

Samples

3 6 3
1 3 1
1 2 2
2 3 3
2 3 4
1 3 8
1 3 10

6

Constraints

$1\le n,m,k\le 10^5$ $1\le u,v\le n$ $1\le w\le 10^9$

Resources

2021 UESTC ICPC Training for Graph