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
ebraheemahmed:
20180813 00:00:37
I'm using Dijkstra and got WA at 15th test cases , why ?!?!? 

soham_12345:
20180703 15:03:06
why spfa gives WA? 

straw__hat:
20180524 15:17:02
I'm getting tle on 15th test case. Don't know why? :( 

sharif ullah:
20180104 17:31:25
easy one....normal dijikstra works! no need optimized dijikstra for small weight,,,,


thuong_2210:
20171212 14:56:11
ledacthuongvq 

morass:
20170912 00:39:42
@Min_25: You are right  thanx so much. I've fixed it! Have nice day ^_^ 

Min_25:
20170910 09:17:28
@morass


shubham_001:
20170629 10:52:37
Those trying with Dijkstra:


dnverma:
20170318 14:39:40
after 15 its give internal error why?


morass:
20170314 14:41:29
@danish4200: The testcase you TLE is "just slow" (so the program won't cycle anywhere). So well  it seems the algorithm is slow  so you either have to improve it (make your Dijkstra faster  which is possible) /or/ you have to think up new approach (which was intended but both are possible  {by checking what is difference in statement and in "general" Dijkstra})

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