题目内容

AI超节点打破以GPU为中心的架构，所有计算单元通过总线或直接互连，是更高效、更灵活的全对等架构。

1. 超节点内部的计算单元，彼此间存在互联通道或没有。
2. 每一条互联通道因为距离、材质、老化等原因，其通信时延不同。
3. 不同计算单元通信时，其通信时延为所经过的每段通道的时延累加。例如一条计算单元通信的路径需要经过3条通道，每条通道的附加时延分别为$R1$、$R2$、$R3$，则路径整体的时延 = $R1$ + $R2$ + $R3$。

当前有$K$对任意给定的源节点和目的计算单元，计算其通信最小时延。

输入描述

每个用例的第一行包含两个整数，分别表示计算单元数量$N$（$1 \le N \le 100$）和互联通道数量$M$（$1 \le M <= N*N$），两者之间用空格隔开。

接下来$M$行，每行包含三个整数$a\ b\ c$，表示计算单元$a$和计算单元$b$之间有一条通信时延为$c$（$1 \le c \le 100$）的互联通道。

整数$K$，表示需要计算的$K$对单元之间的最小通信时延。

$K$行，每行两个整数$i, j$，表示需要计算的单元$i$和单元$j$的最小通信时延（$0<=i,j<=N$）。

输出描述

如果不存在可选通信路径，输出$0$。

如果存在，则输出目标计算单元之间的最小通信时延。

样例1

输入

5 3
0 1 10
1 2 20
3 4 40
3
0 2
0 3
3 4

输出

30
0
40

说明

输入： $5\ 3$//$5$个计算单元，$3$条互联通道

$0\ 1\ 10$//计算单元$0$和计算单元$1$之间，存在一条时延为$10$互联通道

$1\ 2\ 20$ $3\ 4\ 40$

$3$//下面有$3$对计算单元需要计算最小通信时延 $0\ 2$ $0\ 3$ $3\ 4$

输出： $30$//计算单元$0$和计算单元$2$之间最小通信时延$30$

$0$//计算单元$0$和计算单元$3$之间没有通信路径

$40$//计算单元$3$和计算单元$4$之间最小通信时延$40$