给您一个加权无向连通图,由 $$$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)$$$。这个三元组意味着在权重为$$$d_i$$$的顶点$$$u_i$$$和$$$v_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$$$ 之间的最短距离。
示例
输入 #1
3 3 1 2 3 2 3 1 3 1 5 3 1 2 1 3 2 3
输出 #1
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
输出 #2
7 5 6 7 7 1 2 7