Розглянемо орієнтований зважений граф, що має \(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