Təpələr arasındakı məsafə

İstiqamətlənməmiş çəkili qraf verilir. İki təpə arasındakı minimal yolun çəkisini tapmalı.

Giriş verilənləri

Giriş faylının ilk sətri $n$, $m$, $s$ və $f(n\le 5000,m\le 10^5,1\le s,f\le n,s\ne f)$ natural ədədlərini ehtiva edir, uyğun olaraq - təpələrin sayı, tillərin sayı, aralarındakı məsafənin tapılması tələb olunan təpələrin nömrələri.

Növbəti $m$ sətir $b_i$, $e_i$ və $w_i$ natural ədədlərini ehtiva edir, uyğun olaraq — $i$-ci tilin uclarının nömrəsi və onun çəkisi $(1\le b_i,e_i\le n,0\le w_i\le 10^5)$.

Çıxış verilənləri

İlk sətirdə bir natural ədəd veilməli — $s$ və $f$ təpələri arasındakı minimal yolun çəkisi. İkinci sətirdə isə boşluqla ayrılmış $s$-dən $f$-ə gedən ən qısa yoldakı təpələri keçilmə ardicilliğı ilə verməli. Əgər $s$-dən $f$-ə yol yoxdursa $-1$ verməli.

Nümunələr