Hạo sẵn lòng kiểm tra những chú bò mỗi ngay. Anh ta đi ngang một số trong \(M\) \((1 \le M \le 50000)\) đường mòn được đánh số từ \(1\) đến \(M\) từ bãi cỏ \(1\), tất cả đường đi đến bãi cỏ \(N\) (một hành trình sẽ tồn trại trong bản đồ trong dữ liệu kiểm tra). \(N\) bãi cỏ \((1 \le N \le 10000)\) được đánh số liên tiếp \(1..N\), trong trang trại của Hạo, được nối bằng những đường mòn hai chiều. Mỗi đường mòn \(i\) nối bãi cỏ \(P1_i\) và \(P2_i\) \((1 \le P1_i \le N; 1 \le P2_i \le N)\) và yêu cầu \(T_i\) \((1 \le T_i \le 1000000)\) đơn vị thời gian để đi qua.

Anh ta muốn sửa lại một số đường mòn trong trang trại để tiết kiệm thời gian trong hành trình của anh ta. Đặc biệt, anh ta sẽ chọn \(K\) \((1 \le K \le 20)\) đường mòn thành đường cao tốc, mà thời gian sẽ giảm xuống \(0\). Hãy giúp Hạo chọn những đường mòn để tối thiểu thời gian từ bãi cỏ \(1\) đến \(N\).

Dữ liệu vào

• Dòng \(1\): Ba số nguyên cách nhau: \(N, M\), và \(K\)
• Dòng \(2..M+1\): Dòng \(i+1\) miêu tả đường mòn \(i\) với ba dấu cách nhau: \(P1_i, P2_i\), và \(T_i\)

Dữ liệu ra

• Dòng \(1\): Chiều dài ngắn nhất sẽ khi sửa không nhiều hơn \(K\) đường mòn

Input 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Output 1

1