The 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$,接下来的 $q$ 行每行输入两个正整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$。
## 输出格式
输出 $q$ 行,第 $i$ 行的输出的应为第 $i$ 次询问的答案。
题目描述
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 $ .
输入输出格式
输入格式
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 $ .
输出格式
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 $ .
输入输出样例
输入样例 #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