Children Trips

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
There's a new trend among Bytelandian schools. The "Byteland Touristic Bureau" has developed a new project for the highschoolers. The project is socalled "Children's Trips".
The project itself is very simple: there are some touristic routes in Byteland, and N touristic campuses (numbered from 1 to N). For the sake of economy, there are exactly N1 road between them. Of course, even having this given, it is possible to travel from any touristic campus to any other one. Moreover, for the sake of safety, each road is no longer than 2 kilometers.
When some student wants to travel, he first chooses his starting campus  he is been delivered there (say) by a helicopter. He chooses his final destination campus as well. From his final destination, he will be transported to his home by (say) a helicopter, again. So that pupil won't travel any extra distance by foot. When the start and the finish are chosen and the pupil is delivered, he starts his moving by the only route. None of pupils is infinitely strong, so first the pupil looks at the map of the touristic routes, and then he chooses the furthest campus on his way that he can reach during the current day (by safety regulations, it is strictly prohibited to sleep not at the campus because there can be a little trouble with werewolves), and moves there. Then the new day begins, and it repeats till the moment when the destination is reached.
Of course, not all the students created equal. Somebody is good in math, somebody in English, somebody in PE. So it's quite natural that all highschoolers has different strengths.
We call the strength is the maximal number of kilometers that the pupil can pass in a day. And now you're given a lot of queries from the children. For every query, you are given the starting campus, the final campus and the strength. You are requested to calculate the number of days for every trip. The map of the campuses and the distances between them will be given to you as well.
Input
The first line of input contains the integer N, denoting the number of campuses.
The next N1 lines contain triples of the form X Y D with the meaning that there is a road between the Xth and the Yth campus with the length D kilometers.
Then there is a line with a single integer M, denoting the number of queries.
Then, there are M lines with the triples of the form S F P with the meaning that the trip starts at the campus S, ends at the campus F and the student has the strength of P.
Output
For every query, please output the number of days on a separate line.
Constraints
 1 ≤ N, M ≤ 100000
 1 ≤ X, Y, S, F ≤ N
 1 ≤ D ≤ 2
 2 ≤ P ≤ 2*N
Example
Input: 5 1 2 1 2 3 2 1 4 2 4 5 1 5 1 5 3 1 3 2 2 5 4 1 2 10 4 5 2 Output: 1 2 1 1 1
Author:  xcwgf666 
Tester:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/TRIPS 
Tags  lca, mediumhard, oct14, xcwgf666 
Date Added:  4082014 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 