Ở vương quốc Cate, nơi những chú mèo đang bình yên sinh sống trong những căn nhà riêng tư của chúng (vì chúng rất chảnh nên không muốn chia sẻ nhà với ai cả). Quốc vương Mandink, một vị vua anh minh, nhận thấy rằng vương quốc của mình thiếu đi sự kết nối giữa các thần dân, một phần vì các con mèo rất chảnh, một phần vì việc đi lại giữa các căn nhà là rất khó khăn. Điều này thật không tốt chút nào cả. Vì vậy, quốc vương quyết định xây một mạng lưới các con đường hai chiều, kết nối các căn nhà lại với nhau.

Sau một vài chuyến khảo sát, quốc vương biết được hiện nay vương quốc Cate đang có ~n~ căn nhà nằm riêng lẻ với nhau, chưa được kết nối bởi bất kỳ con đường nào cả. Quốc vương tiến hành đánh số các căn nhà theo thứ tự ~1, 2, 3,..., n~. Sau đó, quốc vương dựa theo địa hình của vương quốc, liệt kê ra ~m~ con đường có thể xây dựng được. Mỗi con đường kết nối hai căn nhà ~u~ và ~v~ với chi phí xây dựng là ~c~ cho phép việc đi lại thuận tiện giữa hai căn nhà này.

Việc xây dựng các con đường sẽ dẫn đến sự hình thành của các khu phố. Hai căn nhà ~u~ và ~v~ được xem là thuộc cùng một khu phố khi từ ~u~ có thể đi đến ~v~ và từ ~v~ có thể đi đến ~u~ thông qua các con đường. Quốc vương mong muốn vương quốc có chính xác ~k~ khu phố. Với vai trò là một lập trình viên, bạn hãy giúp quốc vương Mandink tìm ra chi phí thấp nhất cho việc làm đường nhé.

Input

Dòng đầu tiên chứa ba số nguyên ~n, m, k~ ~(1 \le n, m \le 10^5, 1 \le k \le n)~, lần lượt là số căn nhà, số con đường khả thi và số khu phố mà quốc vương yêu cầu.

~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u, v, c~ ~(1 \le u, v \le n, 1 \le c \le 10^9)~, mô tả con đường thứ ~i~.

Output

In ra một số nguyên là chi phí thấp nhất cho việc làm đường của quốc vương Mandink.

Dữ liệu vào đảm bảo tồn tại cách chọn đường thoả mãn điều kiện.

Giới hạn

• Subtask ~1~: ~10\%~ số điểm có ~n, m \le 20~.
• Subtask ~2~: ~30\%~ số điểm khác có ~n, m \le 10^5~ và ~k = 1~.
• Subtask ~3~: ~60\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input

5 9 2
1 2 3
2 3 7
1 4 2
3 5 9
4 2 3
4 4 10
1 2 11
3 4 1
2 5 2

Sample Output

5

Giải thích

Các cạnh được chọn là các cạch thứ ~3, 8, 9~.

Cách xây dựng được mô tả bằng hình vẽ dưới đây: