Description

给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。 将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

Format

Input

第一行包含三个整数n,m,k(1<=n<=40，1<=m<=1000，1<=k<=10^18)。 接下来m行，每行三个整数u,v,c(1<=u,v<=n，u不等于v，1<=c<=3)，表示从u出发有一条到v的单向边，边长为c。 可能有重边。

Output

包含一行一个正整数，即第k短的路径的长度，如果不存在，输出-1。

Samples

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

4

Limitation

长度为1的路径有1->2，5->3，4->5。

长度为2的路径有2->3，3->4，4->5->3。

长度为3的路径有4->6，1->2->3，3->4->5，5->3->4。

长度为4的路径有5->3->4->5。