Вам задан взвешенный неориентированный связанный граф состоящий из \(n\) вершин и \(m\) ребер.
Вам нужно ответить на \(q\) запросов, \(i\)-й запрос — найти кратчайшее расстояние между вершинами \(u_i\) и \(v_i\).
Выходные данные
Выведите \(q\) строк.
В \(i\)-й строке должен содержаться ответ на \(i\)-й запрос — кратчайшее расстояние между вершинами \(u_i\) и \(v_i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
|
3
4
1
|
|
2
|
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
|