Demək olar ki, ən qısa yol - çəkili

Qısa yolun başlanğıc nöqtəsindən son nöqtəyə qədər olan ən qısa yolun tapılması, verilmiş nöqtələr dəsti və onları birləşdirən kənarların uzunluqları ilə, artıq yaxşı məlum olan bir məsələdir. Bu, artıq gündəlik həyatımızın bir hissəsidir, çünki ən qısa yolun axtarışı proqramları bu gün geniş istifadə olunur.

Əksər insanlara bu tətbiqlər xoş gəlir, çünki onların həyatını çox asanlaşdırır. Bəlkə də çox asanlaşdırmır.

İndi, demək olar ki, hər kəs GPS-naviqasiya cihazlarına çıxış əldə etdikdə, ən qısa yolu təşkil edən əksər marşrutlar intensiv hərəkət səbəbindən daha yavaş olur. Çünki əksər insanlar eyni yolla getməyə çalışır, artıq bu göstərişlərə əməl etməyə dəyməz.

Bunu nəzərə alaraq, müdiriniz sizdən yalnız onun çıxış əldə edə biləcəyi yeni bir tətbiq hazırlamağınızı xahiş edir. Bu, onun görüşə və ya hər hansı təcili tədbirə vaxtını qənaət edəcək. Proqram ən qısa yolu deyil, demək olar ki, ən qısa yolu tapmalıdır. Demək olar ki, ən qısa yol, başlanğıc nöqtəsindən son nöqtəyə qədər olan elə bir ən qısa yoldur ki, onun heç bir kənarı başlanğıc və son nöqtələr arasında hər hansı bir ən qısa yola aid deyil.

Aşağıdakı şəkildə dairələrlə — məkan nöqtələri və oxlarla — uzunluqları göstərilən bir tərəfli marşrutlar ilə xəritə təqdim olunur. Başlanğıc nöqtəsi $s$ kimi, son nöqtə isə $d$ kimi qeyd olunub. Qalın xətlər ən qısa yola aiddir (bu halda hər biri ümumi uzunluğu $4$ olan iki ən qısa yol var). Demək olar ki, ən qısa yol kəsik xətlərlə göstərilib (ümumi uzunluğu $5$), çünki ardıcıl iki nöqtə arasında heç bir marşrut heç bir ən qısa yola aid deyil. Qeyd edin ki, bir neçə mümkün cavab ola bilər, məsələn, əgər uzunluğu $3$ olan marşrutun uzunluğu $1$ olarsa. Cavab hətta mövcud olmaya bilər.

Giriş verilənləri

Bir neçə testdən ibarətdir. Hər bir testin ilk sətiri xəritədəki nöqtələrin sayını və iki nöqtəni birləşdirən mövcud bir tərəfli marşrutların sayını göstərən iki tam ədəd $n(2\le n\le 500)$ və $m(1\le m\le 10^4)$ ehtiva edir. Hər bir nöqtə $0$-dan $n-1$-ə qədər olan tam ədədlə təyin olunur. İkinci sətir müvafiq olaraq başlanğıc və son nöqtələri göstərən iki tam ədəd $s$ və $d$ ehtiva edir $(s\ne d;0\le s,d<n)$.

Növbəti $m$ sətirin hər biri $u,v$ və $p(u\ne v,0\le u,v<n,1\le p\le 10^3)$ üç tam ədədini ehtiva edir ki, bu da $u$-dan $v$-ə qədər olan bir tərəfli marşrutun mövcudluğunu və məsafəsini göstərir. $u$ nöqtəsindən $v$ nöqtəsinə qədər ən çox bir marşrut mövcuddur, lakin nəzərə alın ki, $u$-dan $v$-ə qədər olan marşrutun mövcudluğu $v$-dən $u$-ya qədər olan marşrutun mövcudluğunu ifadə etmir və əgər belə bir yol varsa, onun uzunluğu fərqli ola bilər. Sonuncu sətir iki sıfır ehtiva edir və emal olunmur.

Çıxış verilənləri

Hər bir test üçün tələblərə uyğun gəlmək mümkün deyilsə, $-1$ və ya tapılan demək olar ki, ən qısa yolun uzunluğunu göstərən bir tam ədəd ehtiva edən bir sətir çıxarın.

Nümunələr