约翰一共有 N 个牧场.由 M 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。

请帮助约翰决定对哪些小径进行升级，使他每天从 1 号牧场到第 N 号牧场所花的时间最短。输出这一最短时间即可。

第1行：三个空格分隔的整数：N、M和K 第2行.M+1：第i+1行用三个空格分隔的整数描述轨迹i：P1_i、P2_i和T_i

一个整数； 注意：改造后最短路径长度不超过K条边

K为1；将试验3->4的时间从100改为0。新的最短路径为1->3->4，总遍历时间现在为1。

数据规模N<=50,M<N * (N-1) ,k小于10