Se da un grafo conexo, simple, no dirigido y ponderado con $N$ vértices y $M$ aristas.

Procese $Q$ consultas para encontrar la distancia más corta entre dos vértices $s$ y $e$.

Entrada

La primera línea contiene el número de vértices $N$ y el número de aristas $M$ separados por un espacio. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

Desde la segunda línea hasta la línea $M+1$, cada línea contiene dos vértices $u$, $v$ conectados por una arista y el peso de la arista $w$, separados por espacios. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

La línea $M+2$ contiene el número de consultas $Q$. $(1 \le Q \le 10^{5})$

Desde la línea $M+3$ hasta la línea $M+Q+2$, cada línea contiene dos vértices $s$ y $e$ para los cuales se debe calcular la distancia más corta, separados por un espacio. $(1 \le s, e \le N)$

Salida

Desde la primera línea hasta la línea $Q$, imprima en cada línea la distancia más corta desde el vértice $s$ hasta el vértice $e$.

Ejemplos

Entrada 1

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

Salida 1

2
4

Entrada 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

Salida 2

4
4
0
5