Розглянемо орієнтований зважений граф, що має ~n~ вузлів і ~m~ ребер. Ваше завдання полягає в тому, щоб обчислити мінімальну довжину шляху від вузла 1 до вузла ~n~ з рівно ~k~ ребрами.

Обмеження

• ~1≤n≤100~
• ~1≤m≤n(n-1)~
• ~1≤k≤10^9~
• ~1≤a,b≤n~
• ~1≤c≤10^9~

Формат вхідних даних

Перший рядок містить три цілі числа ~n~, ~m~ і ~k~: кількість вузлів і ребер, а також довжину шляху. Вузли пронумеровані ~1,2,…,n~.

Потім є ~m~ рядків, що описують ребра. Кожен рядок містить три цілі числа ~a, b, c~: існує ребро від вузла ~a~ до вузла ~b~ з вагою ~c~.

Формат вихідних даних

Виведіть мінімальну довжину шляху. Якщо таких шляхів немає, вивести -1.

Приклад вхідних даних

3 4 8
1 2 5
2 3 4
3 1 1
3 2 2

Приклад вихідних даних

27