题目描述

某國的公路網由 $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$ 對起終點，請寫程式計算每對起終點之最佳旅程使用到的最長公路長度，或者回報不存在任何一種路徑的選擇方式。

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