Pusheen has been dreaming about tuna sashimi! She has decided that she needs to eat more tuna in her life, so she decides to go on a tuna tour to eat tuna sashimi and tuna nigiri!

Pusheen has made a note of $N$ restaurants serving tuna sashimi and tuna nigiri and has made plans to eat at many of them! She has $Q$ trips planned - on trip $i$, she will start by eating lunch at restaurant $s_i$ and then walk over to restaurant $e_i$ for dinner.

The $N$ restaurants are connected by $M$ bidirectional roads that Pusheen can walk along in either direction. Pusheen is excited to eat as much tuna sashimi and tuna nigiri as possible, so she wants to know the length of the shortest path between each of these restaurants. Pusheen will not need her helicopter for this, as it is guaranteed that she can walk from any restaurant to any other restaurant along these roads.

Constraints

$2\le N\le 5\cdot {10}^4$

$N-1\le M\le N+200$

$1\le a_i,b_i\le N$, $a_i\ne b_i$

There will be at most one road between two restaurants.

It is possible to reach any restaurant from any other restaurant via the given roads.

$1\le w_i\le {10}^3$

$1\le Q\le 5\cdot {10}^4$

$1\le s_i,e_i\le N$, $s_i\ne e_i$

Input Specification

The first line contains two space-separated positive integers, $N$ and $M$.

$M$ lines follow, each containing three space-separated positive integers, $a_i$, $b_i$, and $w_i$, indicating a bidirectional road of length $w_i$ between restaurants $a_i$ and $b_i$.

A single line follows with a single positive integer, $Q$.

$Q$ lines follow, each containing two space-separated positive integers, $s_i$ and $e_i$, indicating that Pusheen's $i$th trip will be between restaurants $s_i$ and $e_i$.

Output Specification

Output $Q$ lines. On the $i$th line, compute the length of the shortest path for Pusheen's $i$th trip.

Sample Input

3 3
1 2 1
2 3 2
1 3 4
2
1 2
1 3

Sample Output

1
3