Cho một đồ thị vô hướng, có trọng số gồm \(n\) đỉnh và \(m\) cạnh. Tìm trọng số đường đi ngắn nhất từ \(1 \)đến \(n\) nếu có thể thực hiện thao tác sau không quá \(k\) lần:

• Gán trọng số \(0\) cho một cạnh bất kì.

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u,v,w\), có cạnh trọng số \(w\) nối \(u\),\(v\).

Output

• In ra trọng số đường đi ngắn nhất từ \(1\) đến \(n\), hoặc in ra \(-1\) nếu không có đường đi.

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le c \le 10^9\)
• \(0 \le k \le 5\)

Sample Input 1

3 3 1
1 2 1
2 3 2
1 3 3

Sample Output 1

0