Задачі
Відстань між вершинами
Відстань між вершинами
\textit{Коль Дейкстрý писать без кучи,}
\textit{То тайм-лимит ты получишь...}
\textit{А в совсем другой задаче}
\textit{Юзай кучу Фибоначчи!}
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\textit{Спектакль преподавателей ЛКШ.июль-2007}
Задано неорієнтовний зважений граф. Потрібно знайти вагу мінімального шляху між двома вершинами.
\InputFile
Перший рядок містить два натуральних числа $n$ та $m~(1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5)$ --- кількість вершин та кількість рёбер відповідно. Другий рядок містить натуральні числа $s$ та $t~(1 \le s, t \le n, s \ne t)$ --- номери вершин, довжину шляху між якими потрібно знайти.
Наступні $m$ рядків містять описи ребер по одному у рядку. Ребро номер $i$ описується трьома цілими числами $b_i, e_i$ та $w_i~(1 \le b_i, e_i \le n, 0 \le w_i \le 100)$ --- номерами кінців ребра та його вага відповідно.
\OutputFile
Вивести вагу мінімального шляху між вершинами $s$ та $t$, або $-1$, якщо такого шляху немає.
\includegraphics{https://static.e-olymp.com/content/45/4553e1879d5b2920b67d19be8688d1057e1ce444.gif}
Вхідні дані #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Вихідні дані #1
3