帕秋莉正在红魔馆的地下图书馆构建一套魔导传输网络。该网络由 个编号为 的魔导单元组成，单元之间通过 条双向传输通道进行信息交换。 每条通道连接两个特定的单元，并具有一定的传输延迟 。由于魔导路径的复杂性，同一对单元之间可能存在多条不同的通道。 咲夜需要协助帕秋莉计算特定单元对之间的最小传输总延迟。如果两个单元之间存在多条路径，咲夜必须找出总延迟之和最小的一条；若两个单元之间没有任何路径相连，则认为它们无法建立通信。

输入描述:

第一行包含两个整数 ()，分别表示魔导单元的数量和传输通道的数量。 接下来的 行，每行包含三个整数 ()，表示单元 与单元 之间存在一条双向传输通道，其延迟为 。 接下来的一个整数 ()，表示咲夜需要进行的查询次数。 接下来的 行，每行包含两个整数 ()，表示询问单元 与单元 之间的最小传输总延迟。

输出描述:

输出共 行。对于每组查询，输出一个整数表示最小延迟。若两单元间不存在任何路径，则输出 。