URI Online Judge | 1592

Elias and Golias

By Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil

Timelimit: 1

There are many cities connected by roads. The N cities are named with numbers from 0 to N-1. Golias wants to travel by car from his city, identified by the number 0, to the capital, identified by the number N-1 to visit his friend Elias. Each road is one-way and costs an amount of gas.

Given the configuration of the cities and roads, Golias wants to know the minimum amount of fuel he needs, and he also wants to visit at most K different cities. The initial and destination cities also count, it is, he will always need to visit at least two cities.

Input

The first line contains an integer T (T = 200) indicating the number of test cases.

For each test case, the first contains three integers, N (2 ≤ N ≤ 50* or 2 ≤ N ≤ 1000**), M (1 ≤ M ≤ 200* or 1 ≤ M ≤ 3000**) and K (2 ≤ K N), indicating the number of cities, roads and the maximum number of different cities that he may visit, respectively. The next M lines will have three integers A (0 ≤ A N-1), B (0 ≤ B N-1) and C (1 ≤ C ≤ 105) indicating that there is a one-way road that connects the city A to city B , and costs C units of fuel. There might be more than one road connecting the cities, or a road that connects the city to itself.

*for around 90% of the cases;
**for the other test cases.

Output

Output the minimum ammount of fuel possible for each case in a single line, and if Golias can't reach Elias, output -1.

Sample Input Sample Output

3

5 5 3

0 1 2

0 2 1

1 4 3

2 3 1

3 4 2

3 2 2

0 1 1

1 2 1

3 3 2

0 1 1

1 2 1

0 2 3

5

-1

3