Farmer John muốn lắp đường dây điện thoại tại trang trại. Tiếc là công ty điện thoại không hợp tác, nên ông phải trả tiền cho một số dây cáp cần để nối trang trại với hệ thống điện thoại.

Có $N$ cột điện thoại đứng lẻ loi, $(1 \le N \le 1,000)$, rải rác trên đất của ông và được đánh số thuận tiện $1..N$; chưa có cáp nào nối chúng. Tổng cộng $P$ cặp cột, $(1 \le P \le 10,000)$, có thể nối bằng cáp; các cặp còn lại cách nhau quá xa.

Cáp thứ $i$ có thể nối hai cột khác nhau $A_i$ và $B_i$, với độ dài $L_i$ đơn vị nếu được dùng, $(1 \le L_i \le 1,000,000)$. Dữ liệu đầu vào không bao giờ nêu một cặp {$A_i,B_i$} quá một lần. Cột $1$ đã nối với hệ thống điện thoại, và cột $N$ ở trang trại. Cần nối các cột $1$ và $N$ bằng một đường đi gồm cáp; những cột khác có thể được dùng hoặc không.

Công ty sẵn sàng cung cấp miễn phí cho Farmer John $K$ dây cáp, $(0 \le K < N)$. Ngoài ra, ông phải trả mức giá bằng độ dài dây cáp dài nhất còn cần (mỗi cặp cột nối bằng một dây cáp riêng), hoặc $0$ nếu không cần cáp bổ sung.

Hãy xác định số tiền nhỏ nhất Farmer John phải trả.

Dữ liệu vào

Đọc đầu vào từ đầu vào chuẩn.

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

• Các dòng $2..P+1$: dòng $i+1$ chứa ba số nguyên cách nhau bởi dấu cách: $A_i$, $B_i$ và $L_i$.

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn.

• Dòng 1: một số nguyên, là số tiền nhỏ nhất Farmer John có thể trả. Nếu không thể nối trang trại với công ty điện thoại, in $-1$.

Ví dụ

Dữ liệu vào 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Dữ liệu ra 1

4

Ghi chú

Có 5 cột. Cột $1$ không thể nối trực tiếp với cột $4$ hoặc $5$. Cột $5$ không thể nối trực tiếp với cột $1$ hoặc $3$. Mọi cặp khác đều có thể nối. Công ty sẽ cung cấp một dây cáp miễn phí.

Nếu nối cột $1$ với $3$, cột $3$ với $2$, và cột $2$ với $5$, Farmer John cần cáp dài $4$, $3$ và $9$. Công ty sẽ cung cấp dây dài $9$, nên dây còn cần dài nhất có độ dài $4$.

Tác giả bài toán: Paul Christiano, 2007