C. HSPANTREE – Cây khung nhỏ nhất

Cho đồ thị vô hướng liên thông, có trọng số có đỉnh, cạnh, cạnh có trọng số . Hãy tìm cây khung nhỏ nhất (cây khung có tổng trọng số trên các cạnh nhỏ nhất) của đồ thị .

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên và là số đỉnh và số cạnh của ;
• dòng tiếp theo, mỗi dòng chứa ba số số cho biết một cạnh nối hai đỉnh và trong và trọng số tương ứng.

Dữ liệu ra:

• Dòng đầu ghi một số nguyên là tổng trọng số của cây khung;
• dòng tiếp theo, mỗi dòng ghi hai số mô tả một cạnh của cây khung.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

5
2 1
3 1
4 2
5 2
6 3

Giới hạn:

• .