URI Online Judge | 1592
# Elias and Golias

**Timelimit: 1**

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

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.

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

For each test case, the first contains three integers,

*for around 90% of the cases;

**for the other test cases.

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 |