Shikhar Sharad is fascinated by Harry Potter and plans on visiting Hogwarts School of Witchcraft and Wizardry.
He would want to find the cheapest flight or flights that would take him to Hogwarts.
He knows that a direct flight to Hogwarts, if one exists, would be way too expensive, so he is willing to tolerate a certain number of stopovers. Since there is a long lists of flights, he wants your help to find the least expensive way to reach there.
You will be given two numbers N and M where N denotes the number of cities he is considering ( 0 being his home and N-1 being Hogwarts) and M denotes the total number of flights.The cities are ordered from "nearest" to "farthest" , Hogwarts being the farthest from his home.There will never be a flight from a "farther" to a "nearer" city.
Finally you are provided with a number of queries. Each query is an integer representing the maximum number of stopovers Shikhar would tolerate on his journey to Hogwarts.
For each query , you must print the least cost of flights that would take him to Hogwarts with no more than the given number of stopovers.
First Line contains T denoting the number of Test cases .
Each Test case begins with two Integers on 1 line N, M denoting the number of cities and number of available flights.
Next M lines gives the list of flights in the format
x y cwhere y>x and there is a direct flight from x to y with cost c.
Next Line contains an Integer Q denoting the Number of queries.
Next line contains Q space separated Integers each denoting the maximum number of stopovers.
For each Test case you have to output Q lines.Each line would either be minimum cost of reaching Hogwarts with no more than the given number of stopovers or "Not Possible" (Quotes for clarity) if it is not possible.
T <= 111
2 <= N<= 100
0 <= M<= 1000
0 <= Q <= N-1
0 <= (x,y) <= N-1
0 <= c <= 10000
y > x for all Flights
0 1 125
0 2 300
1 3 325
1 2 100
0 3 875
2 3 175
2 1 0
0 1 300
1 2 325
Note: There may be multiple (x,y) pairs with different c values so there may be multiple flights between 2 cities but with a different cost
Problem Setter : Arjun Singh Bhatia