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
ashish_2495:
20200526 18:32:54
EVERYTHING OF MINE IS CORRECT INSTEAD IT IS GIVING WA IN RUNNING 15TH TEST CASE


binario:
20200524 16:16:22
If you are given TLE and you is using set/map, try a implementation without it. The constant of the redBlackTree is very high and the time limit for this problem is very tight. 

s_piyush:
20200518 18:03:51
normal dijkstra works! 

thewatch:
20200424 12:51:46
getting TLE on the 15th test case while using normal Dijkstra. 

chiri4:
20200407 04:23:32
How many cases are there ? Should we read input until empty line or something ? I am getting error reading the input in the 15 case. Any clue ? I am using Java


kkmeliodus:
20190801 15:22:46
Use optimised dijikstras for small weight otherwise you will get TLE with normal Dijikstras otherwise they would not have given such constraints. Link for approach is http://www.geeksforgeeks.org/dialsalgorithmoptimizeddijkstraforsmallrangeweights/


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,,,,

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