Đề bài: Tối thiểu chi phí kéo dây điện thoại

Farmer John (FJ) dự định kéo một đường dây điện thoại đến trang trại của mình, nhưng công ty viễn thông không có ý định cung cấp dịch vụ miễn phí cho ông. Do đó, FJ phải trả một khoản phí nhất định cho công ty viễn thông để kéo đường dây này.

Có ~ N ~ (~ 1 \leq N \leq 1,000 ~) cột điện thoại được đánh số từ ~ 1 ~ đến ~ N ~. Hiện tại không có đường dây điện thoại nào kết nối giữa hai cột điện thoại. Có tổng cộng ~ P ~ (~ 1 \leq P \leq 10^6 ~) cặp cột điện thoại có thể kết nối với nhau bằng các đường dây điện thoại, với mỗi cặp có chi phí nhất định. Dữ liệu đảm bảo rằng mỗi cặp ~ \{A_i, B_i\} ~ chỉ xuất hiện một lần.

Công ty viễn thông đã đồng ý kết nối miễn phí ~ K ~ (~ 0 \leq K < N ~) cặp cột điện thoại. Nếu số lượng cột điện thoại cần kết nối không vượt quá ~ K ~, thì tổng chi phí của FJ là ~ 0 ~. Hãy tính toán số tiền tối thiểu mà FJ cần phải chi.

Input

• Dòng 1: 3 số nguyên cách nhau bởi dấu cách ~ N, P, K ~.
• Dòng 2 đến ~ P+1 ~: Mỗi dòng chứa 3 số nguyên ~ A_i, B_i, L_i ~, biểu diễn một đường dây điện thoại giữa cột ~ A_i ~ và ~ B_i ~ với chi phí ~ L_i ~.

Output

• Dòng 1: Xuất ra một số nguyên, là chi phí tối thiểu mà FJ phải chi. Nếu không thể kết nối tất cả các cột, xuất -1.

Ví dụ

Input

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

Output

4

Giải thích

• Tổng cộng có 5 cột điện thoại bị bỏ hoang.
• Đường nối miễn phí ~ K = 1 ~, do đó, FJ có thể yêu cầu miễn phí một cặp cột điện thoại.
• FJ chọn cách nối: ~ 1 \to 3 \to 2 \to 5 \to 4 ~, sử dụng các đường có chi phí thấp nhất.