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