Chọn thành phố trung tâm

Đấ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. Các tuyến đường không cắt nhau, tuyến đường thứ $i$ nối giữa hai thành phố khác nhau $a_i$ và $b_i$ và có khoảng cách $c_i$ (với $i=1,\dots ,M$). Hai thành phố có thể được nối bởi nhiều tuyến đường; khi đó đi theo tuyến nào cũng được. Khoảng cách giữa hai thành phố là tổng độ dài của đường đi ngắn nhất giữa chúng (khoảng cách từ một thành phố đến chính nó bằng $0$).

Ô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.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên $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ố nguyên $a_i,b_i,c_i$ ($1\le a_i,b_i\le N$; $a_i\ne b_i$; $1\le c_i\le {10}^9$).

Dữ liệu ra

Nếu tồn tại hai thành phố nào đó không có đường đi giữa chúng, ghi số duy nhất $0$.

Ngược lại, ghi trên một dòng hai số: tổng khoảng cách nhỏ 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 (số thành phố đạt tổng nhỏ nhất đó).

Ràng buộc

• $1\le N\le 450$, $0\le M\le {10}^5$.
• $1\le a_i,b_i\le N$, $a_i\ne b_i$.
• $1\le c_i\le {10}^9$.

Subtasks

• $30\%$ số test: $N\le {10}^2$, $M\le {10}^2$.
• $30\%$ số test: $N\le {10}^2$, $M\le {10}^5$.
• $40\%$ số test: $N\le 450$, $M\le {10}^5$.

Ví dụ