Cho đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\) và các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) \((1\leq i\leq m)\) có trọng số là \(w_i\). Cho trước số nguyên \(k\), bạn hãy lập trình tính toán độ dài của đường đi đơn ngắn nhất, xuất phát ở đỉnh \(1\) và kết thúc ở đỉnh \(n\), mà có đúng \(k\) cạnh. Một đường đi đơn là đường đi mà không có đỉnh nào được ghé thăm quá một lần.

Input

Dòng đầu chứa ba số nguyên dương \(n\), \(m\), và \(k\).

Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(x_i\), \(y_i\), \(w_i\) mô tả một cạnh vô hướng nối đỉnh \(x_i\) và đỉnh \(y_i\) của đồ thị, với trọng số là \(w_i\). \((x_i \ne y_i)\)

Output

In ra độ dài của đường đi ngắn nhất tìm được. Nếu không tìm được đường đi nào thỏa mãn các ràng buộc ở đề bài thì in ra \(-1\).

Ví dụ

Sample input

6 6 3
1 2 3
2 3 1
3 6 4
1 4 1
4 5 5
5 6 9

Sample output

8

Ràng buộc

Trong tất cả các test:

• \(2\leq n < 10^6\)
• \(1\leq m, k < 10^6\).
• \(1\leq w_i \leq 10^8\).
• Không tồn tại \(i\ne j\) sao cho \(x_i=x_j\) và \(y_i=y_j\).

Subtasks

• Subtask 1: \(\text{min}(n, m, k)\leq 3\).
• Subtask 2: \(\text{min}(n, m, k)\leq 4\).
• Subtask 3: \(\text{min}(n, m, k)\leq 5\).