Đấ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ố ai và bi có khoảng cách ci với i=1..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 1 chứa 2 số N và M.

• M dòng sau, dòng thứ i chứa ba số ai, bi (1 ≤ ai, bi ≤ N) và ci (i=1..M).

Output:

• Gồm một dòng chứa 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 ghi số duy nhất 0.

Sample Input

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

Sample Output

10 2

Giới hạn

1 ≤ N ≤ 450; 0 ≤ M ≤ 10^5; 1 ≤ ci ≤ 10^9