1597_次短路

给出一个有向图，求从 顶点a 到 顶点b 的次短路。

单测试用例。每个测试用例：

第一行是2个正整数 n 和 e，表示该有向图的顶点数和边数。3 < n ≤ 5000 ， 3 < e < 40000 。顶点的编号是 1 ~ n 。

接下来 e 行，每行3个正整数 u , v 和 w ，表示一条从 顶点u 指向 顶点v 的弧，权值为 w

接下来是个正整数 Q，表示接下来有Q个询问。

接下来是Q行，每行2个正整数 a 和 b，表示询问从 顶点a 到 顶点b 的次短路长度。

每个询问输出一行结果：

如果不存在次短路，则输出 no route

否则，输出从 顶点a 到 顶点b 的次短路的长度

5 9
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
5 4 2
6
2 5
1 2
3 1
5 4
1 5
5 2

16
23
21
7
10
23