Để đảm bảo việc cung cấp điện cho các công ty trong một khu công nghiệp, ban quản lý khu công nghiệp lên kế hoạch xây dựng thêm một nhà máy nhiệt điện \(X\). Chỉ có một công ty (bất kì trong khu công nghiệp) sẽ đuợc truyền tải điện từ nhà máy \(X\). Chi phí cho kết nối từ nhà máy nhiệt điện X đến công ty này là không đáng kể. Một công ty được xem là có nguồn điện ổn định nếu nó có kết nối đến nhà máy nhiệt điện \(X\) hay nó có kết nối đến một công ty khác có nguồn điện ổn định. Dựa trên chi phí kết nối giữa các công ty do nhóm khảo sát thực hiện, ban quản lý muốn cân nhắc hai giải pháp kết nối ít chí phí nhất để tất cả các công ty trong khu công nghiệp có nguồn điện ổn định.

Yêu cầu

• Cho biết trước chi phí kết nối giữa các công ty. Hãy xác định tổng chi phí kết nối nhỏ nhất \(S1\) và nhỏ thứ hai \(S2\) giữa các công ty sao cho tất cả các công ty đều có nguồn điện ổn định, (có thể \(S1=S2\) khi có hai cách kết nối giữa các công ty mà chi phí kết nối nhỏ nhất bằng nhau). Giả sử rằng luôn tìm được hai cách kết nối khác nhau để các nhà máy có nguồn điện ổn định.

Dữ liệu vào

• Dòng đầu là hai số nguyên N, M (3≤ N ≤100) lần luợt là số công ty và số kết nối đã được khảo sát giữa các công ty.
• M dòng tiếp theo, mỗi dòng chứa 3 số nguyên Ai, Bi, Ci cho biết để kết nối hai công ty Ai, Bi thì cần chi phí Ci (1≤Ci≤1000). Các công ty được đánh số từ 1 đến N.

Dữ liệu ra

• Hai số nguyên \(S1\) và \(S2\) trên một dòng. Hai số cách nhau một khoảng trắng.

Input 1

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

Output 1

4 5