拉麵市有\(n\)家拉麵店，編號\(0\)到\(n-1\)。

有些拉麵店彼此有道路相連。

Joy家住在\(a\)拉麵店，拉麵學校則開在\(b\)拉麵店。

他每天放學回家之前，會挑一間拉麵店吃晚餐，吃完晚餐才回家。

Joy最近製作了一張吃拉麵日曆，上面共有\(q\)天。

第\(i\)天上面寫著一個數字\(c_i\)，表示他那天要去\(c_i\)拉麵店吃晚餐。

注意到\(c_i\)可以是\(a\)也可以是\(b\)。

他想知道第\(i\)天從學校走到\(c_i\)拉麵店再走到家最短需走多長的路，但是他忙著打音遊沒時間一個個算。

因此他拜託你幫他算出來。

Input

第一行輸入五個正整數\(n,m,q,a,b\)。

接下來輸入\(m\)行。

每行輸入三個正整數\(u,v,w\)，表示\(u\)拉麵店和\(v\)拉麵店之間有一條長度為\(w\)的道路。\((0\le u,v\le n-1,u\neq v,1\le w\le 10^9)\)

接下來輸入\(q\)行。

第\(i\)行輸入一個正整數\(c_i\)。\((0\le c_i\le n-1)\)。

\(2\le n\le 10^{5},1\le q\le 10^{5},n-1\le m\le\min(3\cdot 10^5,\frac{n(n-1)}{2}),0\le a,b\le n-1,a\neq b\)

保證從任一家拉麵店都能走到其他所有的拉麵店。

Output

輸出\(q\)行。

第\(i\)行輸出一個正整數代表從從學校走到\(c_i\)拉麵店再走到家的最短路徑長。

Constraints

第 \(1\) 組測資 \(6\) 分：範例測資。

第 \(2\) 組測資 \(13\) 分：拉麵國的結構是一顆樹且所有道路長都是\(1\)。

第 \(3\) 組測資 \(13\) 分：拉麵國的結構是一顆樹。

第 \(4\) 組測資 \(13\) 分：所有道路長都是\(1\)。

第 \(5\) 組測資 \(27\) 分：\(n,q\le 1000,m\le 2000\)。

第 \(6\) 組測資 \(28\) 分：無特別限制。

Sample Input 1

6 5 6 1 3
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0
1
2
3
4
5

Sample Output 1

4
2
2
2
4
6

Sample Input 2

7 9 7 3 6
0 1 2
1 2 5
2 3 4
3 4 10
4 5 3
5 0 7
0 6 3
6 3 5
2 5 1
0
1
2
3
4
5
6

Sample Output 2

11
14
13
5
21
15
5