题目描述

现在你作为德高地图的一名资深工程师，你负责维护一个先进的导航系统，以确保为用户提供准确而高效的服务。该系统覆盖了本城市所有重要地点，共标记了 $n$ 个地点，每个地点都拥有唯一的编号，从 $1$ 到 $n$。

在城市地图上，这些地点之间存在 $m$ 条明确标注长度的路线，形成了一个复杂的网络。你的任务是确保系统能够快速计算出任意两个地点之间的最短驾车距离，为用户提供便捷的导航体验。 目前，有 $q$ 位用户正使用我们的导航系统，他们需要查询从指定起点到终点的最短驾车路线。

请协助他们确定每条查询的最短距离。

输入格式

第一行包含两个正整数 $n,m$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 地点与 $y$ 地点之间有一条互通的公路，距离为 $z$。

之后输入一个整数 $q$，表示 $q$ 次询问。

最后 $q$ 行，每次询问输入两个整数 $a,b$，表示起点和终点。

$1≤n,x,y,a,b≤100$，$1≤m,q,z≤10000$

$x≠y,a≠b$，且本题的数据中两个地点之间可能有多条路

输出格式

输出 $q$ 行，表示 $q$ 次查询的最短距离，如果 $a$ 与 $b$ 之间非连通，则输出 No path。

4 4
1 2 999
2 1 16
2 3 10
1 3 21
3
3 1
1 2
1 4

21
16
No path

4 4
1 2 999
2 1 16
2 3 10
1 3 666
3
3 1
1 2
1 4

26
16
No path

提示