В авиасети есть n аэропортов и m прямых рейсов. Каждый рейс задан направлением и стоимостью билета.

Нужно добраться из аэропорта s в аэропорт t, потратив как можно меньше денег. При этом разрешено сделать не более k пересадок, то есть использовать не более k + 1 рейса за весь маршрут.

Определите минимальную стоимость такого перелёта.

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

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

Первая строка содержит четыре целых числа n, m, s, t.

Вторая строка содержит одно целое число k.

Каждая из следующих m строк содержит описание одного рейса: три целых числа u, v, w, где u — аэропорт вылета, v — аэропорт прилёта, w — стоимость этого рейса.

Все данные считываются из стандартного ввода.

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

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

Результат следует вывести в стандартный вывод.

Ограничения

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

Примеры

Пример 1

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

2 1 1 2
0
1 2 7

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

7

Пример 2

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

3 3 1 3
0
1 2 1
2 3 1
1 3 10

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

10