Коль Дейкстрý писать без кучи,
То тайм-лимит ты получишь...
А в совсем другой задаче
Юзай кучу Фибоначчи!
___________________________________________
Спектакль преподавателей ЛКШ.июль-2007
Задано неорієнтовний зважений граф. Потрібно знайти вагу мінімального шляху між двома вершинами.
Перший рядок містить два натуральних числа n та m (1≤n≤105,1≤m≤2⋅105) — кількість вершин та кількість рёбер відповідно. Другий рядок містить натуральні числа s та t (1≤s,t≤n,s=t) — номери вершин, довжину шляху між якими потрібно знайти.
Наступні m рядків містять описи ребер по одному у рядку. Ребро номер i описується трьома цілими числами bi,ei та wi (1≤bi,ei≤n,0≤wi≤100) — номерами кінців ребра та його вага відповідно.
Вивести вагу мінімального шляху між вершинами s та t, або −1, якщо такого шляху немає.