题目描述

某國的公路網由 $n$ 個城鎮（編號 $1\sim n$）和 $m$ 條連接兩個相異城鎮的雙向公路組成，每條公路有其長度，以公里表示。最近該國流行起電動車，但是公路之間都沒有充電站，電動車只能在城鎮充電。該國交通部門官員十分擔心有些被觀光局規劃好的旅程會使電動車的續航力沒辦法走完一條公路，也因此，官員希望旅程中使用到的最長公路長度要盡量短，否則若有些電動車的實際續航力低於一段公路的長度，它們一定會在公路中間沒電。

對於一趟被規劃好的旅程，觀光局會為其決定好一個起點 $u$ 和終點 $v$，並找出 $\textbf{兩條}$ 由 $u$ 到 $v$ $\textbf{公路相互不重複}$ 的路徑，來做為一個完整的旅程規劃。例如下圖是一個 $n=7$、$m=9$ 的例子，點上標示城鎮的編號，邊上標示公路的長度。

若要規劃城鎮 $1$ 到城鎮 $2$ 的旅程，可以採用以下兩條路徑：

• $1\to 2$ 以及 $1\to 3\to 2$

這兩條路徑中，所使用的到的最長公路長度是 $8$ 公里，但若採用以下兩條路徑：

• $1\to 2$ 以及 $1\to 3\to 5\to 2$

就可以將使用的最長公路長度降低至 $5$，也是使最長公路最短的選擇方式。而若要規劃城鎮 $1$ 到城鎮 $6$ 的旅程，可以採用以下兩條路徑：

• $1\to 3\to 6$ 以及 $1\to 2\to 5\to 3\to 4\to 6$

使用的最長公路長度是 $7$，同時也是使最長公路最短的選擇方式，注意到雖然這兩條路徑共用了同一個城鎮 $3$，但條件只要求「使用的公路不重複」，因此為一種滿足條件的路徑選擇方式。

一個旅程的兩條路徑所使用的最長公路愈短，則該旅程愈佳。今給定 $q$ 對起終點，請寫程式計算每對起終點之最佳旅程使用到的最長公路長度，或者回報不存在任何一種路徑的選擇方式。

输入格式

$n$ $m$
$a_1$ $b_1$ $l_1$
$a_2$ $b_2$ $l_2$
$\vdots$
$a_m$ $b_m$ $l_m$
$q$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_q$ $v_q$

• $n$, $m$ 分別代表城鎮和公路的數量。
• 第 $i$ 條公路連接著城鎮 $a_i$ 和 $b_i$，且長度為 $l_i$ 公里。
• $q$ 代表預計規劃的旅程數量。
• 第 $i$ 個旅程預計選擇 $u_i$ 作為起點、$v_i$ 作為終點。

输出格式

$p_1$
$p_2$
$\vdots$
$p_q$

• $p_i$ 為一整數
  • 若 $p_i = -1$，則表示不存在路徑的選擇方法可以完整的規劃第 $i$ 個旅程。
  • 否則，$p_i$ 代表在最佳的路徑選擇方式下，第 $i$ 個旅程所使用到的最長公路長度最小值。

7 9
1 2 5
1 3 3
2 3 8
2 5 3
3 4 3
3 5 4
3 6 2
4 6 7
6 7 6
3
1 2
1 6
3 7

5
7
-1

提示

測資限制

• $2 \le n \le 1000$。
• $n - 1 \le m \le \displaystyle\frac{n\times (n-1)}{2}$。
• $1 \le a_i, b_i \le n$，$a_i \ne b_i$。
• $1 \le l_i \le 10^9$。
• 不會有兩條公路連接著相同的一組城鎮。
• $1 \le q \le 5\times 10^5$。
• $1 \le u_i, v_i \le n$，$u_i \ne v_i$。
• 輸入的數皆為整數。
• 保證任兩個城鎮可以透過若干條公路直接或間接抵達。

評分說明

本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。