Để chuẩn bị cho cuộc thi đồng đội trong kỳ thi Olympic tin học sinh viên toàn quốc, Ban tổ chức quyết định thực hiện việc nối mạng ~ n ~ máy tính (được đánh số từ 1 đến ~ n ~) ở các trại để có thể thực hiện việc chấm bài theo yêu cầu của các đội dự giải. Một máy tính ở một trại nào đó được gọi là đã được hoà mạng nếu như nó được nối trực tiếp với máy chủ của Ban tổ chức (máy được đánh số 1 trong số ~ n ~ máy tính nói trên) hoặc được nối với một máy đã được hoà mạng của một trại khác. Ta gọi cách nối mạng là việc thực hiện các kênh nối giữa một số cặp máy sao cho mỗi máy đều được hoà mạng. Do nhiều lý do khác nhau, chỉ có một số máy có thể nối trực tiếp với máy chủ và cũng chỉ có một số máy tính có thể nối trực tiếp được với nhau. Biết chi phí thực hiện các kênh nối này, Ban tổ chức giải cần chọn ra hai cách nối mạng khác nhau với tổng chi phí thực hiện là nhỏ nhất có thể.

Yêu cầu: Xác định các chi phí của hai cách nối mạng với tổng chi phí thực hiện là nhỏ nhất (hai cách với tổng chi phí là nhỏ nhất và nhỏ nhì). Hai cách nối mạng được xem là khác nhau nếu tồn tại ít nhất 1 kênh nối ở cách này không có trong cách kia.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~ n,m ~ được cách nhau bởi dấu cách, trong đó ~ n ~ ~ (3≤n≤1000) ~ là số lượng máy tính nối mạng, ~ m ~ là số kênh nối có thể thực hiện được giữa một số cặp máy trong số chúng ~ (n≤m≤10000) ~.

• Mỗi dòng trong số ~ m ~ dòng tiếp theo chứa ba số nguyên dương ~ ai, bi, ci ~ được ghi cách nhau bởi dấu cách, trong đó ~ ci ~ cho biết chi phí để thực hiện kênh nối máy ~ ai ~ với máy ~ bi, ci≤30000 (i=1,2,...,m) ~.

Giả thiết dữ liệu đảm bảo luôn có cách nối mạng.

Kết quả:

• Ghi hai số nguyên ~ s1, s2 ~ (cách nhau bởi dấu cách) là hai chi phí nhỏ nhất của hai cách nối mạng tìm được, trong đó ~ s1≤ s2, s1 = s2 ~ khi và chỉ khi có ít nhất hai cách nối mạng khác nhau có chung chi phí nhỏ nhất.

Ví dụ:

Input

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66 

Output

110 121