A magician lives in a country which consists of \textbf{N} islands and \textbf{M} bridges. Some of the bridges are magical bridges, which are created by the magician. Her magic can change all the lengths of the magical bridges to the same non-negative integer simultaneously. This country has a famous \textbf{2}-player race game. Player \textbf{1} starts from island \textbf{S_1} and Player \textbf{2} starts from island \textbf{S_2}. A player who reached the island \textbf{T} first is a winner. Since the magician loves to watch this game, she decided to make the game most exiting by changing the length of the magical bridges so that the difference between the shortest-path distance from \textbf{S_1} to \textbf{T} and the shortest-path distance from \textbf{S_2} to \textbf{T} is as small as possible. We ignore the movement inside the islands. Your job is to calculate how small the gap can be. Note that she assigns a length of the magical bridges before the race starts \textit{once}, and does not change the length\textit{during the race}. \InputFile The input consists of several datasets. The end of the input is denoted by ve zeros separated by a single-space. Each dataset obeys the following format. Every number in the inputs is integer. \textbf{N M S_1 S_2 T} \textbf{a_1 b_1 w_1} \textbf{a_2 b_2 w_2} \textbf{...} \textbf{a_M b_M w_M} (\textbf{a_i}, \textbf{b_i}) indicates the bridge \textbf{i} connects the two islands \textbf{a_i} and \textbf{b_i}. \textbf{w_i} is either a non-negative integer or a letter '\textbf{x}' (quotes for clarity). If \textbf{w_i} is an integer, it indicates the bridge \textbf{i} is normal and its length is \textbf{w_i}. Otherwise, it indicates the bridge \textbf{i} is magical. You can assume the following: \begin{itemize} \item \textbf{1} ≤ \textbf{N} ≤ \textbf{1000} \item \textbf{1} ≤ \textbf{M} ≤ \textbf{2000} \item \textbf{1} ≤ \textbf{S_1}, \textbf{S_2}, \textbf{T} ≤ \textbf{N} \item \textbf{S_1}, \textbf{S_2}, \textbf{T} are all different. \item \textbf{1} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{N} \item \textbf{a_i} ≠ \textbf{b_i} \item For all normal bridge \textbf{i}, \textbf{0} ≤ \textbf{w_i} ≤ \textbf{1000000000} \item The number of magical bridges ≤ \textbf{100} \end{itemize} \OutputFile For each dataset, print the answer in a line.