Dany jest prosty, nieskierowany, ważony i spójny graf o $N$ wierzchołkach i $M$ krawędziach.

Przetwórz $Q$ zapytań o najkrótszą odległość między dwoma wierzchołkami $s$ i $e$.

Wejście

W pierwszej linii podano liczbę wierzchołków $N$ oraz liczbę krawędzi $M$, oddzielone spacją. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

Od drugiej linii następuje $M$ linii, z których każda zawiera dwa wierzchołki $u$, $v$ połączone krawędzią oraz wagę krawędzi $w$, oddzielone spacjami. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

W linii $M+2$ podano liczbę zapytań $Q$. $(1 \le Q \le 10^{5})$

Od linii $M+3$ następuje $Q$ linii, z których każda zawiera dwa wierzchołki $s$ i $e$, dla których należy wyznaczyć najkrótszą odległość, oddzielone spacją. $(1 \le s, e \le N)$

Wyjście

Wypisz $Q$ linii, z których każda zawiera najkrótszą odległość między wierzchołkiem $s$ a wierzchołkiem $e$.

Przykład

Wejście 1

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

Wyjście 1

2
4

Wejście 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

Wyjście 2

4
4
0
5