Farmer John tận tâm kiểm tra đàn bò mỗi ngày. Ông đi qua một số trong $M$ $(1 \le M \le 50,000)$ đường mòn, được đánh số $1,\ldots,M$, từ đồng cỏ $1$ đến tận đồng cỏ $N$ (hành trình này luôn thực hiện được với các bản đồ đường mòn trong dữ liệu kiểm thử). Các đồng cỏ trong trang trại của Farmer John, có $N$ $(1 \le N \le 10,000)$ đồng cỏ và được đánh số $1,\ldots,N$, hiện được nối bằng những đường mòn đất hai chiều. Mỗi đường mòn $i$ nối đồng cỏ $P1_{i}$ và $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$, và cần $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ đơn vị thời gian để đi qua.

Ông muốn cải tạo một số đường mòn trong trang trại để tiết kiệm thời gian cho hành trình dài. Cụ thể, ông sẽ chọn $K$ $(1 \le K \le 20)$ đường mòn để biến thành đường lớn, qua đó thực tế giảm thời gian đi qua mỗi đường xuống $0$. Hãy giúp FJ quyết định cải tạo những đường nào để thời gian đi từ đồng cỏ $1$ đến $N$ là nhỏ nhất.

Dữ liệu vào

• Dòng 1: ba số nguyên cách nhau bởi dấu cách: $N$, $M$ và $K$.

• Các dòng $2,\ldots,M+1$: dòng $i+1$ mô tả đường mòn $i$ bằng ba số nguyên cách nhau bởi dấu cách: $P1_{i}$, $P2_{i}$ và $T_{i}$.

Dữ liệu ra

• Dòng 1: độ dài đường đi ngắn nhất sau khi cải tạo không quá $K$ cạnh.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

$K$ bằng $1$; cải tạo đường mòn $3->4$ để mất $0$ thay vì $100$ đơn vị thời gian. Đường đi ngắn nhất mới là $1->3->4$, với tổng thời gian di chuyển lúc này là $1$.

Tác giả bài toán: Percy Liang, 2008