В городе есть n перекрёстков, пронумерованных от 1 до n, и m дорог с односторонним движением. Для каждой дороги известна её длина — неотрицательное целое число.

Требуется определить минимальную суммарную длину маршрута от перекрёстка s до перекрёстка t.

Если добраться из s в t невозможно, выведите -1.

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

В первой строке заданы четыре целых числа n, m, s, t.

В следующих m строках описаны дороги в формате u v w — существует дорога из перекрёстка u в перекрёсток v длиной w.

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

Выведите одно целое число — минимальную длину пути от s до t, либо -1, если такого пути не существует.

Ограничения

• 1 <= n <= 100000
• 0 <= m <= 300000
• 1 <= s, t <= n
• 1 <= u, v <= n
• 0 <= w <= 1000000

Примеры

Пример 1

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

2 1 1 2
1 2 5

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

5

Пример 2

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

4 5 1 4
1 2 10
1 3 1
3 2 2
2 4 3
3 4 100

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

6