P1041我们最好的最短路（shortest）

【题目背景】

风暴散去后，SinCircle 将队伍走过的道路绘成地图。绝大多数道路构成清晰的骨架，只有少量道路穿过遗迹深处，SinCircle 希望借此迅速回答之后的行程安排。

【题目描述】

给定一张包含 $n$ 个结点与 $m$ 条边的无向连通图。图中不存在自环与重边，每条边都有一个正整数长度。

接下来有 $q$ 次询问。每次询问给定两个结点 $u_i,v_i$，你需要求出从 $u_i$ 到 $v_i$ 的最短路长度。

【输入格式】

从文件 $\textbf{\textit{shortest.in}}$ 中读入数据。

输入的第一行包含一个非负整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含两个正整数 $n,m$，分别表示图中的结点数与边数。

接下来 $m$ 行，每行包含三个正整数 $u_i,v_i,d_i$，表示结点 $u_i$ 与 $v_i$ 之间有一条长度为 $d_i$ 的无向边。

下一行包含一个正整数 $q$，表示询问数量。

接下来 $q$ 行，每行包含两个正整数 $u_i,v_i$，表示一次询问。

【输出格式】

输出到文件 $\textbf{\textit{shortest.out}}$ 中。

对于每次询问输出一行一个整数，表示对应两点之间的最短路长度。

【样例 1 输入】

1023 331 2 342 3 153 1 56371 281 392 3

【样例 1 输出】

132431

{{ render(json.dumps('\clearpage'), 'noi') }}

【样例 2 输入】

1028 1331 2 442 3 653 4 164 5 1275 6 386 7 897 8 7101 4 1111 8 3122 6 9132 7 1144 6 3156 8 2168171 5181 7192 3202 8213 7223 4236 8247 8

【样例 2 输出】

1725364757617287

【说明/提示】

【样例 1 解释】

从结点 $1$ 到结点 $3$ 时，经过结点 $2$ 的路径长度为 $3+1=4$，短于直接相连的长度 $5$。

【样例 2 解释】

例如，从结点 $1$ 到结点 $5$ 的最短路可以依次经过结点 $4,6$，总长度为 $1+3+3=7$。

【样例 3】

见选手目录下的 $\textbf{\textit{shortest/shortest3.in}}$ 和 $\textbf{\textit{shortest/shortest3.ans}}$。

该组样例符合测试点 $1\sim 2$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{shortest/shortest4.in}}$ 和 $\textbf{\textit{shortest/shortest4.ans}}$。

该组样例符合测试点 $3\sim 4$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{shortest/shortest5.in}}$ 和 $\textbf{\textit{shortest/shortest5.ans}}$。

该组样例符合测试点 $5\sim 6$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{shortest/shortest6.in}}$ 和 $\textbf{\textit{shortest/shortest6.ans}}$。

该组样例符合测试点 $7\sim 10$ 的数据范围。

【数据范围】

注意本题特殊的数据范围。

对于全部测试数据，保证 $1\leq n,m,q\leq 10^5$，$m-n\leq 20$，$1\leq d_i\leq 10^9$。

特殊性质 A：保证给出的图是一棵树。