All Submissions


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.

Input
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 c where 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.

Output
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.

Constraints
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

Sample Input
2
4 6
0 1 125
0 2 300
1 3 325
1 2 100
0 3 875
2 3 175
3
2 1 0
3 2
0 1 300
1 2 325
1
0


Sample Output
400
450
875
Not Possible


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

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0