ADATRIP  Ada and Trip
Ada the Ladybug loves trips. She travels around world taking photos and souvenirs. This week she went to Buganda. Common Tourist would surely travel around main city and some conurbations, but Ada has different politics. She wants to go as far as possible (because photos from outlying places are much more valuable).
Problem is, that Buganda is very large so she can barely guess such places. Luckily, you are around so she asked you for help. Can you tell her, how far and how many cities are most distant (if the shortest path is used)?
Input
The first line will contain three integers 1 ≤ N ≤ 5*10^{5}, 0 ≤ M ≤ 10^{6}, Q, the number of cities in Buganda, the number of roads and number of queries (possible arrival cities).
Then M lines follow, with three integers 0 ≤ A, B < N, 0 ≤ L ≤ 10, A, B are cities, which the (bidirectional) road connets and L is length of the road.
Afterward, Q lines follow, each with number 0 ≤ q_{i} < N, meaning the city of arival.
You are asured that max(N,M)*Q will be always lesser/equal than 10^{7}
Gentle warning: Since we are in real world and not in some "graph theory", multiedges and selfedges are completely valid!
Output
For each query print two numbers: The distance of most distant place(s) and number of such places.
Example Input
10 10 10 1 1 1 1 2 1 1 2 3 3 1 1 5 4 10 8 5 10 5 6 5 6 7 3 6 9 3 9 7 4 0 1 2 3 4 5 6 7 8 9
Example Output
0 1 1 2 2 1 2 1 20 1 10 2 15 2 18 2 20 1 18 2
Most distant cities (explanation)
0 2 3 3 2 8 4 8 4 8 4 8 4 4 8
hide comments
me_flawful:
20210901 17:44:35
TLE with sets and AC with Priority Queue. 

amitgupta1999:
20210521 10:20:56
if getting WA of test 15 then , check if all distances are infinite then print 0 1;


anurag_mishra:
20210508 18:37:51
STORE THE ANSWER FOR EVERY INDEX IF QUERY REPEATS PRINT THAT , THIS WILL SOLVE TLE ON 15TH TEST CASE 

maruf_hasan:
20210325 09:43:37
Time Limit is 5.5s but my accepted solution took 39.54s?What's I am missing?


abdulahad0308_:
20210324 05:07:15
SPOJ does not show which testcase you passed and which ones you failed. If it gives WA after running till 15 the WA could have occurred anywhere. 

ravikumar88:
20210211 18:17:22
i am new to graphs i am not getting this? 

mamba_:
20210203 10:05:42
No need of Dial's Algorithm, use Dijkstra implemented using heaps. Getting AC. 

yaseenmollik:
20201021 03:10:31
I don't know why you guys are getting WA at 15th test case. Simple Dijkstra worked for me! 

vineetjai:
20200819 05:58:39
for 15th who are getting WA should consider that distant can be zero while number of such places can be >1 

ashish_2495:
20200526 18:32:54
EVERYTHING OF MINE IS CORRECT INSTEAD IT IS GIVING WA IN RUNNING 15TH TEST CASE

Added by:  Morass 
Date:  20170209 
Time limit:  5.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 