Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(M\) con đường. Mỗi con đường nối hai thành phố khác nhau và có thể đi theo cả hai chiều. Từ bất kỳ thành phố nào cũng có thể đi đến bất kỳ thành phố nào khác bằng các con đường này. Tất cả các con đường ở JOI đều là đường thu phí, và mỗi con đường có một mức phí riêng.

Đất nước JOI cũng tổ chức Olympic Tin học. Mỗi thành phố cử một thí sinh đại diện tham dự vòng chung kết. Cần quyết định những thành phố sẽ tổ chức vòng chung kết và ước tính chi phí đưa các thí sinh đến đó. Vòng chung kết được tổ chức tại \(K\) thành phố; khi vòng chung kết diễn ra, mọi thí sinh phải có mặt tại một trong các thành phố được chọn. Không có giới hạn về số thí sinh tập trung tại một thành phố.

Các thí sinh sử dụng đường bộ để đến nơi tổ chức vòng chung kết. Với một con đường có mức phí \(c\), dù có bao nhiêu người cùng đi qua trong một lượt thì phí của lượt đó vẫn là \(c\). Vì vậy, có thể tiết kiệm chi phí bằng cách sắp xếp thứ tự di chuyển để nhiều thí sinh cùng đi qua một con đường trong một lượt.

Yêu cầu

Hãy chọn các thành phố tổ chức vòng chung kết và cách đưa các thí sinh đến đó sao cho tổng phí đường bộ phải trả là nhỏ nhất. Cho \(N,M,K\) và thông tin về tất cả các con đường, hãy viết chương trình tính tổng phí nhỏ nhất này.

Dữ liệu vào

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

• Dòng đầu chứa ba số nguyên \(N,M,K\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) mô tả con đường thứ \(i\), gồm ba số nguyên \(A_i,B_i,C_i\), cách nhau bởi dấu cách. Con đường này nối hai thành phố \(A_i\) và \(B_i\), có mức phí \(C_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng phí nhỏ nhất để đưa tất cả các thí sinh đến các thành phố tổ chức vòng chung kết.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le100\,000\): số thành phố.

• \(1\le M\le100\,000\): số con đường.
• \(1\le K\le N\): số thành phố tổ chức vòng chung kết.
• \(1\le A_i<B_i\le N\) với \(1\le i\le M\).
• \(1\le C_i\le100\) với \(1\le i\le M\).
• Từ bất kỳ thành phố nào cũng có thể đi đến bất kỳ thành phố nào khác bằng đường bộ.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) nhóm kiểm thử, mỗi nhóm \(10\) điểm. Có tất cả \(12\) bộ dữ liệu: hai nhóm có \(2\) bộ dữ liệu mỗi nhóm, tám nhóm còn lại có \(1\) bộ dữ liệu mỗi nhóm. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên tất cả các bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

Các nhóm test dưới đây có thể chồng lấp:

• Các nhóm test có tổng cộng \(40\) điểm thỏa mãn \(N\le1\,000\).
• Các nhóm test có tổng cộng \(40\) điểm thỏa mãn \(K=1\).
• Các nhóm test có tổng cộng \(20\) điểm thỏa mãn đồng thời \(N\le1\,000\) và \(K=1\).
• Các nhóm test có tổng cộng \(60\) điểm thỏa mãn ít nhất một trong hai điều kiện \(N\le1\,000\) hoặc \(K=1\).

Ví dụ

4 3 1
1 2 2
2 3 9
2 4 5

16

5 6 2
1 2 5
1 3 3
2 3 4
2 5 7
3 4 6
4 5 5

12