Shortest path queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
With the impressive achievement in competitive programming Jem was offered an internship at IBER  a tech company that provides an alternative to tradditional taxi service.
Jem first task was help IBER quickly calculate the distance between two arbitrary locations in Jem's city. As an experienced competitive programmer Jem understand that this is not a trivial problem with general graph. Fortunately after investigate the city map Jem found out that the roads system is have a special form which may make Jem's problem easier to deal with.
There are N locations in the city and M bidirectional road connecting them. Each road i have the length of C_{i} and no two road connect the same pair of locations. The roads system is designed in a way that from a specific location one can travel to any other locations. The most important point is that there is no location belong to more than one cycle in the graph corresponding to road network.
So Jem already got his solution. If you want to secure an internship at IBER maybe you can try to solve this problem too!
Input
 The first line of the input contains two number N and M
 In the next M line each line contains three numbers u, v and c represent a road of length c connects location u and v.
 Next line contains a single number Q represents the number of queries.
 In the next Q lines each line contains two numbers u and v corresponding to a query of the length of the shortest path between location u and v.
Output
For each query print out the corresponding result in one line.
Constraint
 2 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 2 × 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ c ≤ 10^{4}
Example
Input 1: 4 3 1 2 2 2 3 3 2 4 4 2 1 4 4 3 Output 1: 6 7 Input 2: 7 8 1 2 2 1 3 4 2 3 1 3 4 1 4 5 1 4 7 1 5 6 2 6 7 1 3 1 4 5 7 1 6 Output 2: 4 2 6
Explaination
Test 2: the graph is shown in the picture below.
The shortest path for each query are:
 From 1 to 4: 1 > 2 > 3 > 4
 From 5 to 7: 5 > 4 > 7
 From 1 to 6: 1 > 2 > 3 > 4 > 7 > 6
Author:  tuananh93 
Tester:  errichto 
Editorial  http://discuss.codechef.com/problems/TACTQUER 
Tags  cook74, dynamicprogramming, graph, hard, tuananh93 
Date Added:  9092016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, 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. 