T. Z 小花的狗村

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

由于营养过剩，Z 小花村里的狗全都体重超标。为了狗子们的健康着想，Z 小花决定让狗子们跑步减肥。村里可以简化为编号从 $1$ 到 $n$ 的 $n$ 个不同地点，地点之间有 $m$ 条双向道路。每条路的承重量有限，如果狗子的体重超过承重量，就会把路压坏！

Z 小花一共安排了 $k$ 条跑步线路，他想知道对于每条跑步线路而言，能够承受的最大重量是多少。

第 1 行是两个整数 $n, m$ 。表示有 $n$ 个地点， $m$ 条道路。

接下来 $m$ 行每行三个整数 $x, y, z$ ，用一个空格隔开。表示从地点 $x$ 到地点 $y$ 有一条承重量为 $z$ 的道路。可能存在重边，没有自环。

接下来一行有一个整数 $k$ ，表示有 $k$ 条跑步线路。

接下来 $k$ 行，每行两个整数 $x, y$ ，用一个空格隔开，表示一条跑步线路从地点 $x$ 到地点 $y$ ，保证 $x \neq y$ 。

输出 $k$ 行，每行一个整数，表示每条线路能够承受的最大重量。如果不存在合法的线路，输出 -1。

3
-1
3

对于 $100\%$ 的数据， $1 \le n \le 10^4$ ， $1 \le m \le 5 \times 10^4$ ， $1 \le k \le 3 \times 10^4$ ， $0 \le z \le 10^5$ 。