CF1051F.The Shortest Statement

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$.

给你一个带权无向连通图，包含 $n$ 个顶点和 $m$ 条边。

你需要回答 $q$ 个查询，其中第 $i$ 个查询要求计算顶点 $u_i$ 与 $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$.

第一行包含两个整数 $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)$ 组成。该三元组表示在顶点 $u_i$ 与 $v_i$ 之间存在一条权值为 $d_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$。

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$.

输出 $q$ 行。

第 $i$ 行应包含第 $i$ 个查询的答案——顶点 $u_i$ 与 $v_i$ 之间的最短距离。