You are given a simple undirected weighted connected graph with $N$ vertices and $M$ edges.

Process $Q$ queries to find the shortest distance between two vertices $s$ and $e$.

The first line contains the number of vertices $N$ and the number of edges $M$, separated by a space. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

From the second line, $M$ lines follow, each containing two vertices $u$ and $v$ connected by an edge, and the weight of the edge $w$, separated by spaces. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

The $(M+2)$-th line contains the number of queries $Q$. $(1 \le Q \le 10^{5})$

From the $(M+3)$-th line, $Q$ lines follow, each containing two vertices $s$ and $e$ for which the shortest distance must be found, separated by a space. $(1 \le s, e \le N)$

For each of the $Q$ queries, output the shortest distance from vertex $s$ to vertex $e$ on a new line.

Examples

Input 1

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

Output 1

2
4

Input 2

6 8
1 2 1
3 1 2
2 3 2
5 2 1
3 5 4
5 4 5
2 6 3
4 2 3
4
1 6
4 1
5 5
6 3

Output 2

4
4
0
5