1031 - MST

Description

Bài toán yêu cầu trong số các cây khung nhỏ nhất của một đồ thị vô hướng hãy tìm và đưa ra cây khung có thứ tự từ điển nhỏ nhất.

Định nghĩa thứ tự từ điển của 1 cây khung:

• Cây khung được biểu diễn bởi chuỗi các cạnh của cây khung đó; 
• Mỗi cạnh được viết theo chỉ số nhỏ đến chỉ số lớn: (u,v), u<v; 
• Các cạnh của cây khung được liệt kê từ cạnh có chỉ số nhỏ đến chỉ số lớn, cạnh (u1,v1) đi trước cạnh (u2,v2) nếu u1<u2hoặc (u1=u2 và v1<v2).

Input

Dòng đầu chứa hai số nguyên dương n ≤ 10⁵, m ≤ 10⁵ là số cạnh và số đỉnh của đồ thị; 

m dòng sau mỗi dòng chứa ba số nguyên dương u, v và c tương ứng là một canh (u,v) và trọng số c trên cạnh.

Output

Dòng đầu tiên chứa 1 số nguyên là trọng số của cây khung tìm được. 

Dòng thư hai chứa n-1 cặp số là các cạnh của cây khung tìm được, liệt kê theo thứ tự từ chỉ số nhỏ đến chỉ số lớn của từng cạnh.

Sample Input

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

Sample Output

9 
1 2 1 4 2 3 

Hint

Source

• Submit
• Summary
• Discuss