Miss Worm
By Ricardo Anido 
Brazil
By Ricardo Anido Brazil
Miss Worm is furious when she hears people say worms are palindrome animals, for which one cannot distinguish head from tail. What an outrageous lie!
Miss Worm lives in a beautiful cave, composed of chambers and tunnels. Each tunnel connects two different chambers and can be used in both directions. A cycle in the cave is a sequence of chambers s1, s2, . . . , sn, sn+1 = s1 , where si ≠ si+1 and (si, si+1 ) is a tunnel, for 1 ≤ i ≤ n. Miss Worm’s cave may contain cycles, but each chamber is part of at most one cycle. Tunnels and caves are rather cramped, so that if some part of Miss Worm’s body is already ocuppying a tunnel or a cave, there is no room for Miss Worm to re-enter that tunnel or cave.
Some cave chambers have access from the surface. Miss Worm has a map that describes the cave, informing the length of each tunnel and which two chambers each tunnel links. Miss Worm is also self-councious and knows her exact length.
Miss Worm wants to know, for the chambers that have access to the surface, if it is possible to enter the cave by that chamber, walk the minimum possible distance inside the cave and leave the cave by the same chamber, moving always ahead, never moving backwards. Can you help her?
The input contains several test cases. The first line of a test case contains two integers S (2 ≤ S ≤ 104 ) and T (1 ≤ T ≤ 2S) representing respectively the number of chambers and the number of tunnels in the cave. Chambers are identified by integers from 1 to S. Each of the next T lines describes a tunnel and contains three integers A, B and C (1 ≤ A < B ≤ S; 1 ≤ C ≤ 100), where A and B represent the chambers connected by the tunnel, and C represents the tunnel’s length. No chamber is connected to more than 100 other chambers. The next line contains an integer Q (1 ≤ Q ≤ 100), which indicates the number of queries. Each of the next Q lines describes a query and contains two integers X (1 ≤ X ≤ S) and M (1 ≤ M ≤ 105 ), indicating respectively the chamber Miss Worm wants to enter the cave and the length of Miss Worm’s body.
For each query in the input your program must produce a single line, containing a single integer, the length of the shortest walk Miss Worm must tread to enter and leave the cave by the chamber indicated in the query, moving always ahead, never moving backwards. If that is not possible, the line must contain the value −1.
| Sample Input | Sample Output |
|
4 4 |
47 |