F. Самое короткое условие
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан взвешенный неориентированный связанный граф состоящий из $$$n$$$ вершин и $$$m$$$ ребер.

Вам нужно ответить на $$$q$$$ запросов, $$$i$$$-й запрос — найти кратчайшее расстояние между вершинами $$$u_i$$$ и $$$v_i$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m~(1 \le n, m \le 10^5, m - n \le 20)$$$ — количество вершин графа и количество ребер графа.

В следующих $$$m$$$ строках заданы рёбра: $$$i$$$-е ребро задаётся тройкой целых чисел $$$v_i, u_i, d_i~(1 \le u_i, v_i \le n, 1 \le d_i \le 10^9, u_i \neq v_i)$$$. Эта тройка означает, что между вершинами $$$u_i$$$ и $$$v_i$$$ есть ребро веса $$$d_i$$$. Гарантируется, что граф не содержит петель и кратных рёбер.

Следующая строка содержит целое число $$$q~(1 \le q \le 10^5)$$$ — количество запросов.

Следующие $$$q$$$ строк содержат по два целых числа $$$u_i$$$ и $$$v_i~(1 \le u_i, v_i \le n)$$$ — описания запросов.

Обратите внимание на необычное ограничение $$$m - n ~ \le ~ 20$$$.

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

Выведите $$$q$$$ строк.

В $$$i$$$-й строке должен содержаться ответ на $$$i$$$-й запрос — кратчайшее расстояние между вершинами $$$u_i$$$ и $$$v_i$$$.

Примеры
Входные данные
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
Выходные данные
3
4
1
Входные данные
8 13
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
8
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8
Выходные данные
7
5
6
7
7
1
2
7