On donne un graphe connexe, simple, non orienté et pondéré, composé de $N$ sommets et $M$ arêtes.

Traitez $Q$ requêtes consistant à trouver la distance la plus courte entre deux sommets $s$ et $e$.

Entrée

La première ligne contient le nombre de sommets $N$ et le nombre d'arêtes $M$, séparés par un espace. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

À partir de la deuxième ligne, $M$ lignes décrivent les arêtes, chacune contenant deux sommets $u$ et $v$ ainsi que le poids de l'arête $w$, séparés par des espaces. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

La ligne $M+2$ contient le nombre de requêtes $Q$. $(1 \le Q \le 10^{5})$

À partir de la ligne $M+3$, $Q$ lignes décrivent les requêtes, chacune contenant deux sommets $s$ et $e$ pour lesquels la distance la plus courte doit être calculée, séparés par un espace. $(1 \le s, e \le N)$

Sortie

Affichez, sur $Q$ lignes, la distance la plus courte entre le sommet $s$ et le sommet $e$ pour chaque requête.

Exemples

Entrée 1

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

Sortie 1

2
4

Entrée 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

Sortie 2

4
4
0
5