Đất nước Omega có ~N~ thành phố (đánh số từ ~1~ đến ~N~) và ~M~ tuyến đường hai chiều nối giữa các thành phố này. Hai thành phố được nối tối đa bởi một tuyến tại hai đầu mút, các tuyến đường không cắt nhau, tuyến đường thứ ~i~ nối giữa thành phố ~a_i~ và ~b_i~ có khoảng cách ~c_i~ với ~i=1,\dots,M~.

Ông Piter vừa được bầu chọn làm tổng thống mới của Omega và kế hoạch đầu tiên của ông cho sự phát triển kinh tế là xây dựng các trung tâm kinh tế lớn tại các thành phố mà việc đi lại, giao thương buôn bán phải dễ dàng.

Trong rất nhiều tiêu chí chọn thành phố đặt các trung tâm kinh tế, ông Piter quyết định những thành phố được chọn phải có tổng khoảng cách đến các thành phố khác là nhỏ nhất.

Yêu cầu: Tìm các thành phố thỏa mãn quyết định của ông Piter.

Input

• Dòng đầu ghi hai số ~N~ và ~M~ ~(1 \le N \le 450; 0 \le M \le 10^5)~;

• ~M~ dòng sau, dòng thứ ~i~ ghi ba số ~a_i, b_i, c_i~ ~(1 \le a_i, b_i \le N; 1 \le c_i \le 10^9; i=1,\dots,M)~.

Output

Một dòng ghi tổng khoảng cách ngắn nhất từ một thành phố được chọn đến các thành phố khác và số lượng thành phố được chọn. Nếu tồn tại hai thành phố nào đó không có đường đi, ghi số duy nhất ~0~.

Scoring

Sample Input 1

4 4
1 2 2
1 3 3
2 4 3
3 4 10

Sample Output 1

10 2