顾神牛收拾好行李后准备前往目的地了，顾神牛的所在地跟目标地点处在一个n个顶点m条边的有向图中。对于每条边(a，b)，如果顶点a和b在同一个强连通分支上则可以坐车，沿着该边从a到达b的时间是time[a][b]，否则需要步行，沿着该边从a到达b的时间是2*time[a][b]。顾叔叔体力有限，希望在k次步行内从起点0尽快到达终点n-1。

第一行包含三个整数，分别是n，m，k，后面接着m行，每行三个整数a，b，c，表示存在边(a,b)，坐车经过该边的时间为c。

输出仅一个整数，如果从顶点0出发，经过不超过k次步行，不能到达顶点n-1，则输出-1，否则输出最短时间。

5 6 3
0 1 1
0 2 2
2 1 1
1 3 3
3 1 3
3 4 2

9

JSOI2012春季函授A层次考试题