The Shortest Statement
Description
You are given a weighed undirected connected graph, consisting of $n$ vertices and $m$ edges.
You should answer $q$ queries, the $i$-th query is to find the shortest distance between vertices $u_i$ and $v_i$.
The first line contains two integers $n$ and $m~(1 \le n, m \le 10^5, m - n \le 20)$ — the number of vertices and edges in the graph.
Next $m$ lines contain the edges: the $i$-th edge is a triple of integers $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)$. This triple means that there is an edge between vertices $u_i$ and $v_i$ of weight $d_i$. It is guaranteed that graph contains no self-loops and multiple edges.
The next line contains a single integer $q~(1 \le q \le 10^5)$ — the number of queries.
Each of the next $q$ lines contains two integers $u_i$ and $v_i~(1 \le u_i, v_i \le n)$ — descriptions of the queries.
Pay attention to the restriction $m - n ~ \le ~ 20$.
Print $q$ lines.
The $i$-th line should contain the answer to the $i$-th query — the shortest distance between vertices $u_i$ and $v_i$.
Input
The first line contains two integers $n$ and $m~(1 \le n, m \le 10^5, m - n \le 20)$ — the number of vertices and edges in the graph.
Next $m$ lines contain the edges: the $i$-th edge is a triple of integers $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)$. This triple means that there is an edge between vertices $u_i$ and $v_i$ of weight $d_i$. It is guaranteed that graph contains no self-loops and multiple edges.
The next line contains a single integer $q~(1 \le q \le 10^5)$ — the number of queries.
Each of the next $q$ lines contains two integers $u_i$ and $v_i~(1 \le u_i, v_i \le n)$ — descriptions of the queries.
Pay attention to the restriction $m - n ~ \le ~ 20$.
Output
Print $q$ lines.
The $i$-th line should contain the answer to the $i$-th query — the shortest distance between vertices $u_i$ and $v_i$.
3 3<br>1 2 3<br>2 3 1<br>3 1 5<br>3<br>1 2<br>1 3<br>2 3<br>
8 13<br>1 2 4<br>2 3 6<br>3 4 1<br>4 5 12<br>5 6 3<br>6 7 8<br>7 8 7<br>1 4 1<br>1 8 3<br>2 6 9<br>2 7 1<br>4 6 3<br>6 8 2<br>8<br>1 5<br>1 7<br>2 3<br>2 8<br>3 7<br>3 4<br>6 8<br>7 8<br>
3<br>4<br>1<br>
7<br>5<br>6<br>7<br>7<br>1<br>2<br>7<br>