NTICKETS  Nlogonian Tickets
You live in Nlogonia, a country that has N cities connected by some bidirectional roads (as usual). In Nlogonia, there is exactly one path between any pair of cities.
You can't use the roads during your travels for free. There is an officer at each road that will let you use it only if you show him a certain number of tickets. If you don't have the required amount of tickets, you just can't use that road.
The officer will not keep the tickets, though. You need to show the tickets to him, but you can keep them after that. This indicates that you can use the same ticket in more than one road, if you want to.
You are given a description of the road system of Nlogonia and a number of queries. For each query, find the minimum number of tickets you must have to go from a city A to a city B. Consider that city A is the only place where you can buy tickets, so you must be holding all the tickets you will need during the travel before leaving city A.
Input
Each test case starts with a line containing the integer N (2 ≤ N ≤ 10^{5}), the number of cities in Nlogonia. The cities are numbered from 1 to N.
Each of the next N1 lines contains the description of a road, A B T (1 ≤ A, B ≤ N, A ≠ B, T ≤ 10^{9}), indicating that there's a road between the cities A and B, and you must show T tickets to use it. It's guaranteed that no pair of cities will appear more than once in the input.
The next line contains the integer Q (1 ≤ Q ≤ 5×10^{5}), the number of queries. Each of the next Q lines contains two city numbers A B (1 ≤ A, B ≤ N, A ≠ B).
The last test case is followed by a line containg the number 0.
Output
For each query A B, print the minimum number of tickets needed during the travel from city A to city B. Print a blank line after each test case.
Example
Input: 6
1 2 1
1 3 5
3 4 3
3 5 8
1 6 2
3
2 6
5 2
4 6
0
Output:
2
8
5
hide comments
abhinav_jain02:
20190517 14:52:06
Use fast i/o and LCA


joe85123:
20190323 17:20:11
time limit is really strict....


yashkodesia:
20181217 13:06:14
AC in 2nd go due to harsh time limits! :( 

sherlock11:
20180627 21:21:56
after so much of effort finally AC:)............... 

narek:
20180619 02:32:10
tle :( also using LCA


humbletheif:
20180616 23:26:43
I used lca and getting correct output for the above test case...but WA when submitting the solution..Am i missing something important??

Added by:  Ricardo Oliveira [UFPR] 
Date:  20121201 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  UFPR/Own problem 