Дан простой неориентированный взвешенный связный граф с $N$ вершинами и $M$ ребрами.

Обработайте $Q$ запросов на поиск кратчайшего расстояния между двумя вершинами $s$ и $e$.

Входные данные

В первой строке заданы количество вершин $N$ и количество ребер $M$, разделенные пробелом. $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

Со второй строки следуют $M$ строк, каждая из которых содержит два конца ребра $u$, $v$ и вес ребра $w$, разделенные пробелом. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

В строке $M+2$ задано количество запросов $Q$. $(1 \le Q \le 10^{5})$

Начиная со строки $M+3$, следуют $Q$ строк, каждая из которых содержит две вершины $s$ и $e$, для которых необходимо найти кратчайшее расстояние, разделенные пробелом. $(1 \le s, e \le N)$

Выходные данные

Для каждого из $Q$ запросов выведите кратчайшее расстояние от вершины $s$ до вершины $e$ на отдельной строке.

Примеры

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