提示: 欢迎访问OurACM平台。
Problem 2173 Nostop

Accept: 132    Submit: 520
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

M国有N个城市,H条单向的道路,AekdyCoin从编号为1的城市出发,每经过一条道路要花一个单位的时间。假设他出发的时刻为0,他需要在K时刻到达编号为N的城市。并且,AekdyCoin不会在一个城市停留,每到一个城市他要立刻往下一个城市出发,最后在K时刻时他必须在城市N。虽然AekdyCoin经过任意一条道路的花费的时间都是1,但是每条道路的过路费不一定相同。现给出每条道路的过路费,问AekdyCoin从编号为1的城市出发,在K时刻到达编号为N的城市最小需要花费多少钱?注意AekdyCoin可以经过同一个城市任意多次,包括城市N。

Input

第一行输入一个整数T表示数据组数,接下来输入T组数据。对于每组数据,第一行输入三个整数N,H,K(1<=N<=50,1<=H<=3000,1<=K<=1000000000),接下来输入H行,每行三个整数u、v、cost(1<=u,v<=n,1<=cost<=1000000),表示从u到v过路费为cost的一条单行道。

Output

对于每组数据输出一行一个整数表示最小花费,若无法在K时刻到达城市N,则输出-1。

Sample Input

1 5 5 3 1 2 1 2 5 1 1 3 10 3 4 10 4 5 10

Sample Output

30

Submit  Back  Status  Discuss