Problem D
Poor My Problem! :-(

Time Limit: 8 Seconds

To find out what the story of my poor problem is, send an e-mail to [my last name] at gmail.com! :-D

Given the description of a graph, find the minimum-cost path between a source and some targets having the following considerations in mind:

The path can contain at most 1000 edges.
An edge may be used more than one time in the path.
Edges are uni-directional,
A path cost is defined as the sum of its edge costs divided by the number of edges in the path.

Input

There will be several test cases, each starting with three integers in the first line 0 < v <= 600, 0 <= e <= 3600, 0 <= s < v which are respectively the number of vertices, the number of edges and the source vertex. Each of the next e lines contains three integers 0 <= v1 < v, 0 <= v2 < v, 0 <= c <= 100000, which means that there is an edge from vertex v1 to vertex v2 with cost c. Then, there will be an integer q which denotes the number of queries followed by q integers each between 0 and v-1 (inclusive).

Output

For each test case, you must print q lines, each of them consisting two numbers, that are cost of the minimum path from vertex s to corresponding query vertex rounded to four decimal digits, and number of edges in the minimum path. In the case there is no path between them, your program must print "No Path" (without quotations). Print a blank line after each test case. If there are more than one minimum path print out the one with minimum number of edges.

Sample Input Output for Sample Input

3 2 0

0 1 100

1 2 200

5 5 0

0 1 3

1 2 4

2 3 5

2 4 6

4 3 1

0.0000 0

100.0000 1

150.0000 2

3.5000 2

3.5000 4

Problem setter: Hossein Azizpour

1st Amirkabir UT Annual Programming Contest Qualification Round