Вы приехали на горнолыжный курорт с друзьями, чтобы покататься на лыжах. На курорте на определенных высотах оборудованы промежуточные станции. Всего имеется $N$ промежуточных станций, пронумерованных от $1$ до $N$ в порядке убывания высоты. То есть станция $1$ является самой высокой, а станция $N$ — самой низкой.

Сейчас вы с друзьями находитесь на станции $S$. Вы договорились, что каждый из вас может свободно кататься на лыжах, а в конце все встретятся на станции $T$.

На курорте есть $M$ трасс. Каждая трасса ведет от станции $a_i$ к станции $b_i$, и спуск по ней занимает время $t_i$. Трассы всегда ведут в направлении уменьшения высоты, то есть выполняется условие $a_i < b_i$.

Кроме того, на каждой трассе есть подъемник. Подъемник работает в направлении, противоположном трассе (в направлении увеличения высоты). То есть, воспользовавшись подъемником, можно подняться со станции $b_i$ на станцию $a_i$. Вы можете воспользоваться подъемниками не более $K$ раз.

Вы хотите добраться до станции $T$, используя только лыжные трассы и подъемники, при этом максимизировав суммарное время катания на лыжах. Время, проведенное на подъемниках, не учитывается в общем времени катания. По заданной информации о трассах определите максимальное время, в течение которого вы можете кататься на лыжах.

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

В первой строке заданы пять целых чисел $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

В следующих $M$ строках содержится информация о трассах. Каждая строка содержит три целых числа $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$).

Между любыми двумя различными станциями существует не более одной трассы.

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

Выведите одно целое число — максимальное время, в течение которого можно кататься на лыжах.

Если невозможно добраться до станции $T$, как бы вы ни выбирали трассы и подъемники, выведите -1.

Примеры

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

3 2 1 1 3
1 2 10
2 3 5

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

25

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

3 3 1 1 3
1 2 10
2 3 5
1 3 1

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

30

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

3 2 1 3 1
1 2 10
2 3 5

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

-1

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

3 2 2 3 1
1 2 10
2 3 5

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

0