Giải bài trực tuyến

Farmer John sẵn lòng kiểm tra những chú bò mỗi ngay. Anh ta đi ngang một số trong M (1 <= M <= 50,000) đườ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 <= N <= 10,000) được đánh số liên tiếp 1..N, trong trang trại của Farmer John, đượ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 <= P1_i <= N; 1 <= P2_i <= N) và yêu cầu T_i (1 <= T_i <= 1,000,000) đơn vị thời gian để đi qua.

Anh ta muốn sử 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 <= K <= 20) đường mòn thành đường cao tốc, mà thời gian sẽ giảm xuống 0. Hãy giúp FJ chọn những đường mòn để tối thiểu thời gian từ bãi cỏ 1 đến N.

Dữ liệu

* Dòng 1: Ba số nguyên cách nhau: N, M, and 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, and T_i

Kết quả

* 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

Ví dụ

Dữ liệu:

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

Kết quả

1