[POI2015]Wycieczki

时间限制:20s    【提交】    空间限制:128MB

题目描述

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


输入格式

第一行包含三个整数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。
可能有重边。


输出格式

包含一行一个正整数,即第k短的路径的长度,如果不存在,输出-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->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。


题目来源

鸣谢Claris