Máy chủ thứ ba

Hệ thống mạng máy tính của trung tâm Anpha có nhiệm vụ xử lí dữ liệu về giao dịch thương mại điện tử cho các công ty khách hàng. Hệ thống này được đặt ở nhiều tòa nhà khác nhau trong thành phố. Hệ thống gồm có \(N\) máy tính được đánh số tuần tự từ \(1\) đến \(N\). Giữa \(N\) máy tính này có một mạng lưới đường truyền gồm \(M\) đường truyền. Hai máy tính \(x_i, y_i\) bất kì được kết nối trực tiếp với nhau bởi không quá một đường truyền, có chi phí để truyền và xử lí dữ liệu là \(d_i\) (đường truyền hoạt động hai chiều). Trong \(N\) máy tính này thì máy tính \(1\), máy tính \(N\) là hai máy chủ và hệ thống đường truyền đảm bảo luôn có ít nhất một cách truyền và xử lí dữ liệu đi từ máy tính \(1\) đến máy tính \(N\).

Tuy nhiên, cả hai máy chủ của trung tâm Anpha này đều có dấu hiệu quá tải về truyền và xử lí dữ liệu. Vì vậy, Ban giám đốc trung tâm quyết định chọn ra thêm một máy tính nữa trong số các máy tính còn lại để nâng cấp thành một máy chủ thứ ba. Máy tính này sẽ tạm ngừng hoạt động để tiến hành nâng cấp, nhưng trong suốt thời gian nâng cấp yêu cầu phải đảm bảo đường truyền và xử lí dữ liệu với chi phí ít nhất từ máy tính \(1\) đến máy tính \(N\) được thông suốt, nghĩa là chi phí nhỏ nhất để đi từ máy \(1\) đến máy \(N\) khi không dùng máy tính đang nâng cấp vẫn bằng chi phí nhỏ nhất ban đầu, để không hệ thống mạng nào của Trung tâm sẽ bị trì trệ ảnh hưởng đến hoạt động kinh doanh của các công ty khách hàng.

Yêu cầu: Hãy giúp Ban giám đốc trung tâm Anpha xác định các máy tính có thể được chọn làm máy chủ thứ ba sao cho máy tính được chọn thỏa mãn các điều kiện ở trên. Máy chủ thứ ba là một máy tính khác máy \(1\) và máy \(N\).

Input

Dữ liệu vào gồm:

Dòng đầu tiên ghi hai số nguyên dương \(N, M\) là số lượng máy tính và số lượng đường truyền (\(2 \le N \le 3 \cdot 10^4\), \(1 \le M \le 10^5\));
Dòng thứ \(i\) trong số \(M\) dòng tiếp theo ghi ba số nguyên dương \(x_i, y_i, d_i\) với ý nghĩa chi phí truyền và xử lí dữ liệu giữa \(2\) máy tính \(x_i, y_i\) là \(d_i\) (\(1 \le x_i, y_i \le N\); \(1 \le d_i \le 10^3\)).

Ràng buộc:

Có \(80\%\) số test thỏa mãn \(2 \le N \le 3 \cdot 10^3\);
Có \(20\%\) số test thỏa mãn \(3 \cdot 10^3 < N \le 3 \cdot 10^4\).

Output

In ra:

Dòng đầu tiên ghi số nguyên \(S\) là số lượng các máy tính có thể được chọn làm máy chủ thứ ba;
\(S\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương là số thứ tự của máy tính được chọn (in ra theo thứ tự tăng dần).

Example

Input:

Output:

Note

Chi phí nhỏ nhất đi từ máy \(1\) đến máy \(8\) là \(6\), theo hai đường đi \(1 \to 5 \to 6 \to 7 \to 8\) và \(1 \to 2 \to 6 \to 7 \to 8\). Các máy \(6\) và \(7\) nằm trên mọi đường đi ngắn nhất, nên nếu ngừng hoạt động thì chi phí tăng lên (hoặc không còn đường đi). Các máy \(2, 5\) chỉ nằm trên một trong hai đường đi ngắn nhất nên ngừng một máy thì vẫn còn đường đi kia với chi phí \(6\); các máy \(3, 4\) không nằm trên đường đi ngắn nhất nào. Vì vậy có \(4\) máy có thể được chọn là \(2, 3, 4, 5\).

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Note

Bình luận