Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

F. The Shortest Statement
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$.

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$.

Examples
Input
3 31 2 32 3 13 1 531 21 32 3
Output
341
Input
8 131 2 42 3 63 4 14 5 125 6 36 7 87 8 71 4 11 8 32 6 92 7 14 6 36 8 281 51 72 32 83 73 46 87 8
Output
75677127