Вам задан взвешенный неориентированный связанный граф состоящий из \(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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач