Məsələlər
Təpələr arasındakı məsafə
Təpələr arasındakı məsafə
İstiqamətlənməmiş çəkili qraf verilir. İki təpə arasındakı minimal yolun çəkisini tapmalı.
\InputFile
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 \neq 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)$.
\OutputFile
İ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.
\includegraphics{https://static.e-olymp.com/content/45/4553e1879d5b2920b67d19be8688d1057e1ce444.gif}
Giriş verilənləri #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Çıxış verilənləri #1
3 1 2 3