给定一个具有 $N$ 个顶点和 $M$ 条边的简单无向加权连通图。

请处理 $Q$ 次查询，每次查询求出两个顶点 $s$ 和 $e$ 之间的最短距离。

第一行包含两个由空格分隔的整数 $N$ 和 $M$。$(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

接下来的 $M$ 行，每行包含三个由空格分隔的整数 $u$、$v$ 和 $w$，表示连接顶点 $u$ 和 $v$ 的边及其权重 $w$。$(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

第 $M+2$ 行包含查询次数 $Q$。$(1 \le Q \le 10^{5})$

接下来的 $Q$ 行，每行包含两个由空格分隔的整数 $s$ 和 $e$，表示需要求最短距离的两个顶点。$(1 \le s, e \le N)$

输出 $Q$ 行，每行对应一个查询，输出从顶点 $s$ 到顶点 $e$ 的最短距离。

样例

输入格式 1

4 3
1 2 3
4 1 1
3 1 2
2
1 3
4 2

输出格式 1

2
4

输入格式 2

6 8
1 2 1
3 1 2
2 3 2
5 2 1
3 5 4
5 4 5
2 6 3
4 2 3
4
1 6
4 1
5 5
6 3

输出格式 2

4
4
0
5