God

Time Limit: 1000ms

Memory Limit: 65535kb

Description

小明很萌的,你们不要黑他。

小明是个萌汉纸,可整天想着萌妹纸。这不,小明看中了一个非常萌的妹纸,简直就是小明心中的女神,可女神瞬间就消失了。自那以后,小明茶不思,饭不香,日渐消瘦。神看不下去了,告诉小明他的女神所在的城市,还答应免费一部分车费。

小明和女神处在一张无向图中,N(1<=N<=1000)个节点,P(1<=p<=10000)条边。小明在1节点,女神在N节点。小明要从中选择一条路径来找到他的女神。每条道路都有费用li(1<=li<=1000000),神可以为小明支付k(1<=k<=1000)条道路的费用,小明当然很开心啦,可是小明又不是高富帅,接下来的路费之和也可能使小明崩溃。所以,身为基友的你便来帮助小明指定k条免费道路,使之后的路费之和最小。

Input

输入有多组数据,对于每组数据,第一行包含三个数字n,p,k,第二行到第p+1行,每行分别都为三个整数ai,bi,li。

Output

一个整数,表示该项工程的最小支出,如果不可能完成则输出-1。

Sample Input

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Sample Output

5

Hint

None

Source

None

提交代码