根據地震學家嘅預測，Bitland 預計會發生強烈地震。Bitland 有 $n$ 個城市，編號由 $1$ 到 $n$。當中有啲城市由雙向道路連接。我哋將路線視為一串城市，當中每兩個相鄰城市之間都有道路連接。路線嘅長度係沿途所有道路長度嘅總和。城市對 $(a,b)$ 之間嘅最短路線，定義為由城市 $a$ 出發、喺城市 $b$ 結束而長度最短嘅路線。

政府認為核電站（NPP）嘅輻射洩漏係主要問題——一旦發生，就需要疏散居民。每座核電站都位於其中一個城市，總共有 $k$ 座，而每個城市最多只有一座核電站。政府希望制定一個地震期間可行嘅疏散計劃。

城市之間嘅疏散路線應該盡量遠離所有有核電站嘅城市。路線嘅危險度，以路線上各個城市同任何有核電站嘅城市之間嘅最小距離嚟衡量。更正式噉講，設 $(a_1,a_2,\ldots,a_s)$ 係路線上嘅城市，$(g_1,g_2,\ldots,g_k)$ 係有核電站嘅城市，路線嘅危險度就等於所有 $\operatorname{dist}(a_i,g_j)$ 值當中嘅最小值，其中 $\operatorname{dist}(a,b)$ 係 $a$ 同 $b$ 之間最短路線嘅長度。

而家畀你 $Q$ 對城市 $(s_i,t_i)$，你要為每一對城市制定危險度最大嘅疏散計劃。

輸入格式

第一行包含兩個以空格分隔嘅整數 $n$ 同 $m$（$2\le n\le10^5$，$1\le m\le5\cdot10^5$），分別係 Bitland 嘅城市數目同道路數目。跟住 $m$ 行描述道路，每行一條。每條道路由三個數 $a_i,b_i,w_i$（$1\le a_i,b_i\le n$，$1\le w_i\le1000$，$a_i\ne b_i$）表示，分別係所連接嘅兩個城市同道路長度。下一行包含一個整數 $k$（$1\le k\le n$），表示有核電站嘅城市數目。再下一行包含 $k$ 個整數 $g_i$（對所有 $1\le i\le k$，都有 $1\le g_i\le n$），表示核電站所在城市嘅編號。下一行包含一個整數 $Q$（$1\le Q\le10^5$），表示疏散計劃涉及嘅城市對數目。跟住 $Q$ 行，每行畀出第 $i$ 對城市 $(s_i,t_i)$（$1\le s_i,t_i\le n$，$s_i\ne t_i$）。

保證冇道路將一個城市連去自己，任何一對城市之間最多只有一條道路，而且由任何城市出發都可以到達其他任何城市。

輸出格式

輸出 $Q$ 行。

第 $i$ 行輸出一個整數，表示城市對 $(s_i,t_i)$ 嘅最大危險度。

子任務

呢題包含五個子任務：

1. $n\le10^3$，$1\le m\le10^3$，$Q\le10^3$。每一對 $(s_i,t_i)$ 之間都有一條直接連接佢哋嘅道路。佔 10 分。
2. $n\le10^5$，$Q\le10^5$。每一對 $(s_i,t_i)$ 之間都有一條直接連接佢哋嘅道路。佔 13 分。
3. $n\le15$，$1\le m\le200$，$1\le Q\le200$。佔 12 分。
4. $Q=1$。佔 19 分。
5. 使用上文題面嘅限制。佔 46 分。

樣例

輸入格式 1

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

輸出格式 1

5
5
0
7
8

說明