Расстояние между вершинами

Очень простая

Ограничение по времени выполнения 2 секунды

Ограничение по использованию памяти 128 мегабайт

Коль Дейкстрý писать без кучи, То тайм-лимит ты получишь... А в совсем другой задаче Юзай кучу Фибоначчи!

Спектакль преподавателей ЛКШ.июль-2007

Задан неориентированный взвешенный граф. Найдите длину наименьшего пути между двумя заданными вершинами.

Входные данные

Первая строка содержит два натуральных числа $n$ и $m (1 \leq n \leq 1 0^{5}, 1 \leq m \leq 2 \cdot 1 0^{5})$ — количество вершин и рёбер в графе. Вторая строка содержит два натуральных числа $s$ и $t (1 \leq s, t \leq n, s \neq = t)$ — номера вершин, между которыми необходимо найти минимальный путь.

Следующие $m$ строк содержат описание рёбер. Ребро номер $i$ описывается тремя целыми числами $b_{i}, e_{i}$ и $w_{i} (1 \leq b_{i}, e_{i} \leq n, 0 \leq w_{i} \leq 100)$ — номера вершин, которые оно соединяет, и его вес.

Выходные данные

Выведите вес минимального пути между вершинами $s$ и $t$ , или $- 1$ , если пути не существует.

Примеры

Ввод #1

Ответ #1

Отправки 2K

Коэффициент принятия 35 %