Magical Bridges

A magician lives in a country made of $N$ islands and $M$ bridges. Some of the bridges are magical bridges that the magician built. Her magic changes the lengths of all magical bridges at once to the same value, which must be a non-negative integer.

The country has a famous race played by two people. Player 1 starts from island $S_1$ and player 2 starts from island $S_2$. Whoever reaches island $T$ first wins.

The magician enjoys watching this race, so she sets the length of the magical bridges to make the race as close as possible: she minimizes the difference between the shortest-path distance from $S_1$ to $T$ and the shortest-path distance from $S_2$ to $T$. Movement inside an island does not count.

Compute how small that difference can be.

The magician picks the length once before the race starts and never changes it during the race. All magical bridges share the same length. Every bridge can be crossed in either direction.

The input holds several datasets. Each dataset has the format below. Every number in the input is an integer.

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

$(a_i, b_i)$ means bridge $i$ connects island $a_i$ and island $b_i$.

$w_i$ is either a non-negative integer or the letter x. If $w_i$ is an integer, bridge $i$ is a normal bridge of length $w_i$. If $w_i$ is x, bridge $i$ is a magical bridge.

• $1 \le N \le 1000$
• $1 \le M \le 2000$
• $1 \le S_1, S_2, T \le N$
• $S_1$, $S_2$, $T$ are all different.
• $1 \le a_i, b_i \le N$
• $a_i \neq b_i$
• $0 \le w_i \le 1000000000$ for every normal bridge $i$
• The number of magical bridges is at most 100.
• $T$ is reachable from $S_1$ and from $S_2$.

The line after the last dataset holds five zeros separated by single spaces. That line marks the end of the input and is not processed.

For each dataset, print the smallest possible difference between the two shortest-path distances on its own line.