Trong một lần dạo chơi công viên BeeG, Nam phát hiện một trò chơi mới : mê cung. Mê cung gồm N phòng và M hành lang nối giữa các phòng. Mỗi hành lang nối 2 phòng u và v theo được sơn màu c. Bằng hành lang này người ta có thể đi từ phòng u sang phòng v và ngược lại.

Một cuộc tỉ thí sắp được tổ chức. Những người tham gia sẽ bị bịt mắt và thả xuống căn phòng số 1 bằng trực thăng. Nhiệm vụ của người chơi là đến được căn phòng số N (phòng cuối cùng). Một thiết bị theo dõi sẽ được đeo vào mỗi người, ghi lại những căn phòng và hành lang mà người đó đi qua. Người sử dụng ít hành lang nhất để đến căn phòng N sẽ thắng cuộc. Nếu có nhiều người cùng sử dụng ít hành lang nhất, người có đường đi “đẹp” sẽ thắng. Một đường đi được xem là đẹp nếu dãy màu các hành lang mà người đó sử dụng liên tiếp có thứ tự từ điển nhỏ nhất trong tất các các đường đi ngắn nhất.

Quyết tâm giành chiến thắng (vì phần thưởng cực kì hậu hĩnh), Nam thuê hẳn một máy bay trực thăng bay quay công viên BeeG và chụp hình mê cung từ phía trên. Hãy giúp Nam ghi lại đường đi lí tưởng nhất.

Chú ý : Dãy (a1, a2, a3, … , ak) có thứ tự từ điển nhỏ hơn dãy (b1, b2, b3, … ,bk) nếu tồn tại một vị trí i nhỏ nhất (1 <= i <= k) sao cho ai<>bi thì aii.

Giữa hai phòng có thể có nhiều hơn một hành lang.

Input

• Dòng đầu gồm 2 số N, M – số phòng và số hành lang.
• M dòng sau, dòng i gồm 3 số ui  vi  ci thể hiện một hành lang.

Giới hạn :

• 2 <= N <= 100000
• 1 <= M <= 200000
• 1 <= ui , vi <= N
• 1 <= ci<= 10^9

ó 33% số test có N <= 100.

Output

• Dòng đầu ghi K – độ dài đường đi ngắn nhất từ phòng 1 đến phòng N.
• Dòng thứ hai ghi K số là màu của K hành lang theo thứ tự được dùng để đi từ phòng 1 đến phòng N.

Example

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

Output
2
1 3