Məsələlər
Təpələr arasındakı məsafə
Təpələr arasındakı məsafə
\textit{Коль Дейкстрý писать без кучи,}
\textit{То тайм-лимит ты получишь...}
\textit{А в совсем другой задаче}
\textit{Юзай кучу Фибоначчи!}
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\textit{Спектакль преподавателей ЛКШ.июль-2007}
İstiqamətlənməmiş çəkili qraf verilir.
İki təpə arasındakı ən qısa yolun çəkisini tapmaq tələb olunur.
\InputFile
Giriş faylının ilk sətri təpələrin və tillərin sayını ifadə edən iki natural $n$ və $m~(1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5)$ ədədlərini ehtiva edir. Giriş vaylının ikinci sətri aralarındakı uzunluğunu tapmaq tələb olunan təpələrin nömrələrini ifadə edən $s$ və $t~(1 \le s, t \le n, s \ne t)$ natural ədədlərini ehtiva edir.
Növbəti $m$ sətrin hər biri tillərin təsvirini ehtiva edir. $i$ nömrəli til tilin sonluqlarının nömrələrini və onun çəkisini ifadə edən üç tam $b_i, e_i$ və $w_i~(1 \le b_i, e_i \le n, 0 \le w_i \le 100)$ ədədləri ilə ifadə olunur.
\OutputFile
Çıxış faylının yeganə sətri $s$ və $t$ təpələri arasındakı ən kiçik yolun çəkisini ifadə edən yeganə tam ədədı və ya belə yol mövcud deyilsə $-1$ ehtiva etməlidir.
\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