Thành phố quan trọng

Trong một chuyến phiêu lưu xuyên quốc gia, bạn phải đi từ thành phố khởi hành Syrjälä đến thành phố đích Lehmälä. Bạn đã chọn đi bằng máy bay và muốn tìm ra lộ trình có chi phí thấp nhất. Tuy nhiên, trong một số trường hợp, có những thành phố mà bạn chắc chắn phải đi qua nếu muốn tìm được tuyến đường giá rẻ nhất. Hãy xác định các thành phố này.

Dữ liệu về các chuyến bay giữa các thành phố được cung cấp và bạn cần tính toán các thành phố phải đi qua trên tuyến đường giá thấp nhất từ Syrjälä đến Lehmälä.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số thành phố và số chuyến bay. Các thành phố được đánh số \(1, 2, \dots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.

• Dòng tiếp theo là \(m\) dòng, mỗi dòng mô tả một chuyến bay bằng ba số nguyên \(a, b, c\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\) với giá \(c\).

• Tất cả các chuyến bay đều là một chiều.

• Dữ liệu đảm bảo có ít nhất một tuyến đường từ Syrjälä đến Lehmälä.

Output

• Dòng đầu tiên in ra một số nguyên \(k\): số thành phố chắc chắn phải đi qua trong lộ trình giá thấp nhất.

• Dòng tiếp theo in ra \(k\) thành phố đó, sắp xếp theo thứ tự tăng dần.

Example

5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8

4
1 3 4 5