Mê cung có ~n~ phòng đánh số từ ~1~ đến ~n~, được nối với nhau bởi ~m~ đoạn đường đi 2 chiều nối trực tiếp 2 phòng, đường đi thứ ~i~ có màu ~c_i~. Giữa 2 phòng có thể có nhiều đường đi nối trực tiếp. Đường đi trực tiếp có thể nối một phòng với chính nó.

Người chơi được máy bay lên thẳng thả xuống phòng ~1~ và phải tìm đường đi tới phòng ~n~.

• Độ dài của đường đi được tính bằng số đoạn đường nối giữa 2 phòng đã đi qua.
• Ai có đường đi ngắn nhất sẽ thắng cuộc.
• Nếu có nhiều người cùng có đường đi ngắn nhất thì so sánh theo thứ tự từ điển các màu đã đi qua.
• Người có đường đi ngắn nhất với thứ tự từ điển nhỏ nhất sẽ thắng.

Đường đi lý tưởng là đường ngắn nhất và có thứ tự từ điển nhỏ nhất.

Dãy ~a = (a_1, a_2, \dots, a_k)~ được gọi là có thứ tự từ điển nhỏ hơn dãy ~b = (b_1, b_2, \dots, b_k)~ nếu tồn tại số nguyên dương ~i \le k~ sao cho:

• ~a_1 = b_1, a_2 = b_2, \dots, a_{i-1} = b_{i-1}~,
• và ~a_i < b_i~.

Ví dụ: dãy ~a = (1,4,5,3,6,2,3)~ có thứ tự từ điển nhỏ hơn dãy ~b = (1,4,5,4,1,1,2)~ vì 3 phần tử đầu giống nhau và phần tử thứ 4 của ~a~ nhỏ hơn phần tử thứ 4 của ~b~.

Yêu cầu: Cho ~m, n~ và các đường đi ~(u, v, c)~ xác định đường màu ~c~ nối từ phòng ~u~ tới phòng ~v~. Dữ liệu đảm bảo có đường đi từ phòng ~1~ đến phòng ~n~. Hãy xác định đường đi lý tưởng: số đoạn đường và màu của các đoạn đó theo trình tự đi.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n, m~.
• Trong ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~u, v, c~.

Output

• Dòng đầu tiên chứa số nguyên ~k~ – số đoạn đường đi.
• Dòng thứ 2 chứa ~k~ số nguyên – màu của các đoạn theo trình tự đi.

Subtasks

• Subtask 1 (30%): Tất cả các đường đi đều có cùng một màu.
• Subtask 2 (30%): ~1 \le c \le 9, 2 \le n \le 10^2, 1 \le m \le 10^3~.
• Subtask 3 (40%): Không có ràng buộc gì.

Giới hạn

• Subtask 1: ~2 \le n \le 10^5~
• Subtask 2: ~1 \le m \le 2 \times 10^5~
• Subtask 3: ~1 \le u,v \le n~
• ~1 \le c \le 10^9~

Sample Input

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

Sample Output

2
1 3

Giải thích

Có 2 đường đi ngắn nhất từ phòng 1 đến phòng 4 với độ dài 2:

• (1 → 2 → 4) có dãy màu ~(1,4)~.
• (1 → 3 → 4) có dãy màu ~(2,3)~. Ngoài ra còn (1 → 3 → 2 → 4) dài 3, không tối ưu.

So sánh thứ tự từ điển:

• ~(1,4)~ so với ~(2,3)~ → tại phần tử đầu tiên, ~1 < 2~, do đó ~(1,4)~ nhỏ hơn. Vì vậy kết quả là: ~k=2~, dãy màu ~1 3~.