beecrowd | 2130

Worldwide Finals in 2008

By XI Maratona de Programação IME-USP, 2007 BR Brazil

Timelimit: 1

Worried about the current situation of crisis in air transport, the regional director of the ICPC contest in Brazil has already startedhis preparations to make reservations of airline tickets for worldwide finals of Banff in 2008. The first step was to study the available air mesh, in which each flight has a certain price and connects two cities (we are actually calling flight only a snippet of a non stop commercial flight). The Director's goal is to make multiple queries in this mesh of flights.

In general wewant to makenonstop flights, but this can be very expensive. To work around this fact the Directorallowed some possible scales. So, he explained the various towns of the mesh in his order of preference to do thescales. In other words, the index 1 is the city that he prefers to do the scale, followed by City 2, and so on.

The queries that the Director will make are of the following type: is given the city of departure and arrival and a number t of cities in which the Director allows to be made stopovers. Your program must find the minimum cost of a flight between two cities thatdoes at mostscales in these cities. For example, if t = 1 you will find the cost of a flight between the two cities: or non stop or make a stopover in the first city.

Input

The input consists of multiple instances. The first line of each instance consists of two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 100000), indicating the number of cities and the number of scales. In the following m lines, we have three integers u, v and w (u, v ≤ 1 ≤ n and 0 ≤ w ≤ 100) indicating that there is a scale that goes from u to v costing w. Then there is an integer c (1 ≤ c ≤ 10000) indicating the number of queries and the c lines have three integers o, d and t (1 ≤ o, d ≤ n and 1 ≤ t ≤ n) where o is the city of origin, d is the destination city and t indicates that cities 1.2, .., t can be used for stopovers.

The input ends with end of file.

Output

For each instance, you must print a handle Instantance k, where k is the number of the current instance. For each query, in order of entry, you should print the minimum cost or -1 if there is no path between the two cities.

After each instance print a blank line.

Sample Input Sample Output

4 7

4 1 0

2 1 3

1 4 20

2 3 15

4 2 1

3 1 21

1 2 0

3

2 1 0

4 2 2

4 3 1

5 10

4 5 2

2 1 4

1 2 7

2 4 7

5 2 1

4 1 2

4 5 12

5 4 4

5 3 7

3 5 9

4

2 5 0

3 4 5

4 5 1

2 3 2

Instancia 1

3

0

-1

Instancia 2

-1

13

2

-1

XI Maratona de Programação IME-USP, 2007