Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.
Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.
Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.
Входные данные
Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).
Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 109). Между одной парой станций не более одного канала.
Выходные данные
Выведите минимальную мощность либо −1, если передать сообщение за допустимое число переходов невозможно.
Пояснения к примерам
Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.
Пример 2. Связь существует, но сообщение должно пройти два канала, а разрешён только один.
| № | Входные данные | Выходные данные |
|
1
|
5 6 2 1 5
1 2 4
2 5 8
1 3 6
3 4 2
4 5 2
3 5 7
|
7
|
|
2
|
3 2 1 1 3
1 2 0
2 3 0
|
-1
|