마법 다리

어떤 마술사가 사는 나라는 섬 $N$개와 다리 $M$개로 이루어져 있다. 다리 가운데 일부는 마술사가 만든 마법 다리다. 마술사는 마법을 부려 모든 마법 다리의 길이를 동시에 똑같은 값으로 바꿀 수 있고, 그 값은 음이 아닌 정수여야 한다.

이 나라에는 두 사람이 겨루는 유명한 경주 경기가 있다. 1번 선수는 섬 $S_1$에서, 2번 선수는 섬 $S_2$에서 출발한다. 섬 $T$에 먼저 도착한 쪽이 이긴다.

마술사는 이 경기를 즐겨 본다. 그래서 경기가 가장 팽팽해지도록, $S_1$에서 $T$까지의 최단 거리와 $S_2$에서 $T$까지의 최단 거리의 차이가 가장 작아지게 마법 다리의 길이를 정한다. 섬 안에서의 이동은 계산하지 않는다.

이 차이를 얼마나 줄일 수 있는지 구하라.

마술사는 경기가 시작하기 전에 길이를 한 번만 정하고, 경기 도중에는 바꾸지 않는다. 모든 마법 다리의 길이는 서로 같다. 다리는 어느 방향으로든 건널 수 있다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다. 입력에 등장하는 수는 모두 정수다.

N M S1 S2 T
a1 b1 w1
a2 b2 w2
...
aM bM wM

$(a_i, b_i)$는 다리 $i$가 섬 $a_i$와 섬 $b_i$를 잇는다는 뜻이다.

$w_i$는 음이 아닌 정수이거나 문자 x다. $w_i$가 정수면 다리 $i$는 보통 다리이고 길이가 $w_i$다. $w_i$가 x면 다리 $i$는 마법 다리다.

• $1 \le N \le 1000$
• $1 \le M \le 2000$
• $1 \le S_1, S_2, T \le N$
• $S_1$, $S_2$, $T$는 서로 다르다.
• $1 \le a_i, b_i \le N$
• $a_i \neq b_i$
• 보통 다리 $i$는 $0 \le w_i \le 1000000000$
• 마법 다리의 개수는 100 이하다.
• $T$는 $S_1$에서도 $S_2$에서도 갈 수 있다.

마지막 데이터 세트 다음 줄에는 공백 하나로 구분한 0이 다섯 개 주어진다. 이 줄은 입력의 끝을 뜻하며, 처리하지 않는다.

데이터 세트마다 두 최단 거리 차이의 최솟값을 한 줄에 출력한다.