Hãy xem xét một đồ thị đồ có hướng có trọng số gồm có \(n\) nút và \(m\) cạnh. Nhiệm vụ của bạn là tính toán độ dài đường đi tối thiểu từ nút \(1\) đến nút \(n\) với chính xác \(k\) cạnh.

Input

• Dòng đầu vào đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\): số lượng nút và cạnh và độ dài của đường đi. Các nút được đánh số \(1, 2, \ldots, n\).
• Sau đó, có \(m\) dòng mô tả các cạnh. Mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): có một cạnh từ nút \(a\) đến nút \(b\) với trọng số \(c\).

Output

• In độ dài đường đi tối thiểu. Nếu không có đường đi như vậy, hãy in \(−1\).

Constraints

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

Example

Sample input

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

Sample output

27