Thành phố ABC đang lên kế hoạch xây dựng một hệ thống mạng lưới điện để cung cấp điện cho các khu dân cư. Thành phố có ~n~ khu dân cư và một số tuyến đường có thể được xây dựng để nối các khu dân cư với nhau. Mỗi tuyến đường này có một chi phí xây dựng tương ứng.

Mục tiêu của thành phố là xây dựng mạng lưới điện với chi phí thấp nhất nhưng vẫn đảm bảo rằng mọi khu dân cư đều được kết nối với nhau, trực tiếp hoặc gián tiếp.

📝 Yêu cầu bài toán

Bạn được cung cấp:

Số khu dân cư và số tuyến đường khả thi .

Danh sách các tuyến đường, mỗi tuyến đường gồm:

~u~ và ~v~: Hai khu dân cư được kết nối.

~w~: Chi phí xây dựng tuyến đường này.

Yêu cầu:

Tìm tập hợp các tuyến đường cần xây dựng sao cho:

Mọi khu dân cư đều được kết nối.

Tổng chi phí xây dựng là nhỏ nhất.

Xuất ra:

Danh sách các tuyến đường được chọn.

Tổng chi phí tối thiểu.

✅ Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số khu dân cư và số tuyến đường.
• ~m~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~u, v, w~ — biểu thị tuyến đường từ khu dân cư ~u~ đến ~v~ với chi phí ~w~.

✅ Dữ liệu ra

• Dòng đầu tiên in tổng chi phí tối thiểu.
• Tiếp theo, in danh sách các tuyến đường được chọn dưới dạng ~u~ ~v~ ~w~.

📚 Ví dụ

Dữ liệu vào:

4 5
1 2 10
1 3 6
1 4 5
2 4 15
3 4 4

Dữ liệu ra:

19
3 4 4
1 4 5
1 2 10

🔍 Giải thích

Các tuyến đường được chọn là:

• Từ khu 3 đến khu 4 với chi phí 4.
• Từ khu 1 đến khu 4 với chi phí 5.
• Từ khu 1 đến khu 2 với chi phí 10.
• Tổng chi phí tối thiểu là 19.