A91403.Shortest Statement

给你一个有 $n$ 个点，$m$ 条边的无向连通图。有 $q$ 次询问，第 $i$ 次询问回答从 $u_i$ 到 $v_i$ 的最短路的长度。

第一行有两个数 $n$ 和 $m$（$1 \leq n,m \leq 10^5,m-n\leq 20$）。 接下来 $m$ 行包含一条边，输入三个正整数 $u_i,v_i,d_i(1 \leq u_i,v_i \leq n,1 \leq d_i \leq 10^9)$，意思是 $u_i$ 到 $v_i$ 之间有一条长度为 $d_i$ 的边。数据保证不存在自环和重边。下一行再输入一个数 $q$（$1 \leq q \leq 10^5$），接下来的 $q$ 行每行输入两个正整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$。

输出 $q$ 行，第 $i$ 行的输出的应为第 $i$ 次询问的答案。