题目描述

A 国有 $\red{n}$ 座城市，编号从 $\red{1}$ 到 $\red{n}$，城市之间有 $\red{m}$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 $\red{q}$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

输入文件第一行有两个用一个空格隔开的整数 $\red{n}$，$\red{m}$，表示 A 国有 $\red{n}$ 座城市和 $\red{m}$ 条道路。

接下来 $\red{m}$ 行每行 $\red{3}$ 个整数 $\red{x}$、$\red{y}$、$\red{z}$，每两个整数之间用一个空格隔开，表示从 $\red{x}$ 号城市到 $\red{y}$ 号城市有一条限重为 $\red{z}$ 的道路。注意：$\red{x}$ 不等于 $\red{y}$，两座城市之间可能有多条道路。

接下来一行有一个整数 $\red{q}$，表示有 $\red{q}$ 辆货车需要运货。

接下来 $\red{q}$ 行，每行两个整数 $\red{x}$、$\red{y}$，之间用一个空格隔开，表示一辆货车需要从 $\red{x}$ 城市运输货物到 $\red{y}$ 城市，注意：$\red{x}$ 不等于 $\red{y}$。

输出格式

输出共有 $\red{q}$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出 $\red{-1}$。

样例

样例输入 $\red1$

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

样例输出 $\red1$

3
-1
3

数据范围与提示

对于 $\red{30\% }$的数据，$\red{0 < n < 1\,000}$，$\red{0 < m < 10\,000}$，$\red{0 < q < 1\,000}$；

对于 $\red{60\% }$的数据，$\red{0 < n < 1\,000}$，$\red{0 < m < 50\,000}$，$\red{0 < q < 1\,000}$；

对于 $\red{100\%}$ 的数据，$\red{0 < n < 10\,000}$，$\red{0 < m < 50\,000}$，$\red{0 < q < 30\,000}$，$\red{0 \leq z \leq 100\,000}$。