Магічні Мости
Маг живе в країні, що складається з N островів і M мостів. Деякі з цих мостів є магічними, створеними магом. Її магія дозволяє змінювати довжини всіх магічних мостів на одне й те ж саме невід'ємне ціле число одночасно.
У цій країні популярна гра-гонка для 2 гравців. Гравець 1 стартує з острова S_1, а гравець 2 — з острова S_2. Переможцем стає той, хто першим досягне острова T.
Маг, захоплюючись цією грою, вирішила зробити її якомога цікавішою, змінюючи довжини магічних мостів так, щоб різниця між відстанями найкоротших шляхів від S_1 до T та від S_2 до T була якомога меншою. Рух всередині островів не враховується.
Ваше завдання — обчислити, наскільки малим може бути цей розрив.
Зверніть увагу, що довжини магічних мостів призначаються один раз перед початком гонки і не змінюються під час гри.
Вхідні дані
Вхід складається з кількох наборів даних. Кінець вводу позначається п'ятьма нулями, розділеними одним пробілом. Кожен набір даних має наступний формат. Кожне число у вхідних даних є цілим числом.
N M S_1 S_2 T
a_1 b_1 w_1
a_2 b_2 w_2
...
a_M b_M w_M
(a_i, b_i) вказує, що міст i з'єднує два острови a_i і b_i.
w_i є або невід'ємним цілим числом, або літерою 'x' (лапки для ясності). Якщо w_i є цілим числом, це означає, що міст i є звичайним і його довжина w_i. Інакше це означає, що міст i є магічним.
Ви можете припустити наступне:
1 ≤ N ≤ 1000
1 ≤ M ≤ 2000
1 ≤ S_1, S_2, T ≤ N
S_1, S_2, T всі різні.
1 ≤ a_i, b_i ≤ N
a_i ≠ b_i
Для всіх звичайних мостів i, 0 ≤ w_i ≤ 1000000000
Кількість магічних мостів ≤ 100
Вихідні дані
Для кожного набору даних виведіть відповідь в одному рядку.