給定一個具有 $N$ 個頂點與 $M$ 條邊的簡單無向加權連通圖。

請處理 $Q$ 個查詢，每個查詢要求計算兩個頂點 $s$ 與 $e$ 之間的最短距離。

輸入格式

第一行包含兩個整數 $N$ 與 $M$，以空白分隔。$(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

接下來 $M$ 行，每行包含三個整數 $u$、$v$ 與 $w$，分別代表一條邊連接的兩個頂點以及該邊的權重，以空白分隔。$(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

第 $M+2$ 行包含一個整數 $Q$。$(1 \le Q \le 10^{5})$

接下來 $Q$ 行，每行包含兩個整數 $s$ 與 $e$，代表需要計算最短距離的兩個頂點，以空白分隔。$(1 \le s, e \le N)$

輸出格式

輸出共 $Q$ 行，每行對應一個查詢，輸出從頂點 $s$ 到頂點 $e$ 的最短距離。

範例

輸入 1

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

輸出 1

2
4

輸入 2

6 8
1 2 1
3 1 2
2 3 2
5 2 1
3 5 4
5 4 5
2 6 3
4 2 3
4
1 6
4 1
5 5
6 3

輸出 2

4
4
0
5