题目描述

由于营养过剩，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。

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

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$。