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~, …, ~a_k~) được gọi là dãy có thứ tự từ điển nhỏ hơn dãy ~b~ = (~b_1~, ~b_2~, …, ~b_k~) nếu thỏa mãn:

• ~i – 1~ phần tử đầu tiên của hai dãy bằng nhau, tức là ~a_1~ = ~b_1~,~a_2~ = ~b_2~,....,~a_{i-1}~ = ~b_{i-1}~
• Phần tử thứ ~i~ của dãy ~a~ nhỏ hơn phần tử thứ ~i~ của dãy ~b~, tức là ~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 tiên của dãy ~a~ bằng 3 phần tử đầu tiên của dãy ~b~ và phần tử thứ 4 của dãy ~a~ nhỏ hơn phần tử thứ 4 của dãy ~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.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~,
• Dòng thứ ~i~ trong ~m~ dòng sau chứa 3 số nguyên ~u~, ~v~ và ~c~.

*Kết quả: *

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

Ví dụ:

Input

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

Output

2
1 3

*Giới hạn: * 2 ≤ n ≤ ~10^5~,1 ≤ m ≤ 2×~10^5~,1 ≤ u, v ≤ n, 1 ≤ c ≤ ~10^9~

Ràng buộc:

• Subtask1: 30% số test ứng với 30% số điểm của bài tất cả các đường đi đều có cùng một màu.
• Subtask2: 30% số test khác ứng với 30% số điểm của bài có 1 ≤ c ≤ 9, 2 ≤ n ≤ ~10^2~ và 1 ≤ m ≤ ~10^3~.
• Subtask3: 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì.