Магические мосты
Волшебник живет в стране, состоящей из 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
Выходные данные
Для каждого набора данных выведите ответ в отдельной строке.