Cả nước ABC có ~ n ~ thành phố được đánh số từ 1 đến ~ n ~, giữa ~ n ~ thành phố này là một mảng lưới gồm ~ m ~ đường đi hai chiều, mỗi tuyến đường nối 2 trong ~ n ~ thành phố sao cho không có hai thành phố nào được nối bởi quá 1 tuyến đường. Trong các thành phố này thì thành phố 1 và thành phố ~ n ~ là hai trung tâm kinh tế lớn nhất đất nước và hệ thống đường luôn đảm bảo có ít nhất 1 tuyến đường nối liền hai thành phố này. Tuy nhiên cả hai trung tâm này đều có nguy cơ quá tải về mật độ dân số. Vì vậy nhà vua quyết định chọn thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba, thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ tầng. Nhưng trong thời gian sửa chữa ấy phải đảm bảo đường đi ngắn nhất từ thành phố 1 đến thành phố ~n~ không bị thay đổi nếu không nền kinh tế quốc gia sẽ bị trì trễ. Vị trí và đường nối giữa ~ n ~ thành phố được mô tả như một đồ thị ~ n ~ đỉnh và ~ m ~ cạnh. Hãy giúp nhà vua đếm số lượng thành phố làm trung tâm kinh tế thứ 3 sao cho thành phố được chọn thỏa mãn điều kiện ở trên

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương ~ n ~ ~ (2 ≤ n ≤ 30000) ~ và ~ m ~ ~ (1 ≤ m ≤ 100000) ~ là số thành phố và số tuyến đường
• Dòng thứ ~ i ~ trong ~ m ~ dòng tiếp theo ghi 3 số nguyên dương ~ x_i, y_i ~, và ~ d_i ~ với ý nghĩa tuyến đường thứ ~ i ~ có độ dài ~ d_i ~ ~ (1 ≤ d_i ≤ 1000) ~ và nối giữa hai thành phố ~ x_i ~ và ~ y_i ~

Kết quả

• Dòng đầu tiên ghi ~ s ~ là số lượng các thành phố được chọn làm trung tâm kinh tế thứ 3
• ~ s ~ dòng tiếp theo mỗi dòng ghi một số nguyên dương là số thứ tự của thành phố được chọn. (theo thứ tự tăng dần)

Ví dụ:

Input 1

6 6
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100 

Output 1

2
4
5