Sehrli Körpülər
Bir sehrbaz N adadan və M körpüdən ibarət olan bir ölkədə yaşayır. Bu körpülərin bəziləri sehrli körpülərdir və sehrbaz tərəfindən yaradılmışdır. Sehrbaz sehrli körpülərin bütün uzunluqlarını eyni qeyri-mənfi tam ədədə eyni vaxtda dəyişə bilər.
Bu ölkədə məşhur bir 2-oyunçu yarış oyunu var. Oyunçu 1 S_1 adasından, Oyunçu 2 isə S_2 adasından başlayır. T adasına ilk çatan oyunçu qalib olur.
Sehrbaz bu oyunu izləməyi çox sevdiyi üçün sehrli körpülərin uzunluğunu elə dəyişməyə qərar verir ki, S_1-dən T-yə ən qısa yol məsafəsi ilə S_2-dən T-yə ən qısa yol məsafəsi arasındakı fərq mümkün qədər kiçik olsun. Adalar daxilində hərəkəti nəzərə almırıq.
Sizin vəzifəniz bu fərqin nə qədər kiçik ola biləcəyini hesablamaqdır.
Qeyd edək ki, sehrbaz sehrli körpülərin uzunluğunu yarış başlamazdan əvvəl bir dəfə təyin edir və uzunluğu yarış zamanı dəyişmir.
Giriş verilənləri
Giriş bir neçə məlumat dəstindən ibarətdir. Girişin sonu bir boşluqla ayrılmış beş sıfırla göstərilir. Hər bir məlumat dəsti aşağıdakı formata uyğundur. Girişdəki hər bir rəqəm tam ədəddir.
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) körpü i-nin a_i və b_i adalarını birləşdirdiyini göstərir.
w_i ya qeyri-mənfi tam ədəd, ya da 'x' hərfidir (aydınlıq üçün dırnaq içində). Əgər w_i tam ədəddirsə, bu, körpü i-nin normal olduğunu və uzunluğunun w_i olduğunu göstərir. Əks halda, bu, körpü i-nin sehrli olduğunu göstərir.
Aşağıdakıları qəbul edə bilərsiniz:
1 ≤ N ≤ 1000
1 ≤ M ≤ 2000
1 ≤ S_1, S_2, T ≤ N
S_1, S_2, T hamısı fərqlidir.
1 ≤ a_i, b_i ≤ N
a_i ≠ b_i
Bütün normal körpü i üçün, 0 ≤ w_i ≤ 1000000000
Sehrli körpülərin sayı ≤ 100
Çıxış verilənləri
Hər bir məlumat dəsti üçün cavabı bir sətirdə çap edin.