#include <iostream>

 #include <sstream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <set>

 #include <cctype>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <queue>

 #include <map>

 #include <stack>

 #include <list>

 #include <iomanip>

 using namespace std;

 #define INF 0x7fffffff

 #define maxn 100000+10

 int n, m;

 vector<int> g[maxn];//用以存放互相连通的房间

 vector<int> col[maxn];//用以存放走廊颜色

 int step[maxn];//存放由n到i的最短步数

 int ans[maxn*];

 int vis[maxn];

 void init()

 {

     for(int i = ; i < maxn; i++)

     {

         g[i].clear();

         col[i].clear();

     }

     memset(step, -, sizeof(step));

     memset(ans, , sizeof(ans));

     memset(vis, , sizeof(vis));

 }

 //==============获得到n的最少步数(逆向由n到1)===========

 void bfs1()

 {

     queue<int> q;

     q.push(n);

     step[n] = ;//初始，由n到n的最短步数为0

     while(!q.empty())

     {

         int u = q.front(); q.pop();

         int sz = g[u].size();

         for(int i = ; i < sz; i++)

         {

             int v = g[u][i];

             if(v == )

             {

                 step[v] = step[u]+;

                 return ;

             }

             if(step[v] == -)

             {

                 step[v] = step[u]+;

                 q.push(v);

             }

         }

     }

     return ;

 }

 //==========获得最少步数时的最小走廊颜色===========

 void bfs2()

 {

     queue<int> q;

     q.push();

     while(!q.empty())

     {

         int u = q.front(); q.pop();

         ///

         if(!step[u])    return ;//到达n

         ///

         int mmin = INF;

         int sz = g[u].size();

         for(int i = ; i < sz; i++)

         {

             int v = g[u][i];

             if(step[v] == step[u]-)

             {

                 mmin = min(mmin, col[u][i]);//注意理解c[u][i]与g[u][i]间的联系--c[u][i]是u连接g[u][i]的走廊颜色

             }

         }

         //==========以上获得了从1出发最短路中每步的最小色

         int tmp_step = step[] - step[u];//从1到u的步数，即出发第tmp_step步

         //ans[tmp_step] = (ans[tmp_step] == 0 ? mmin : min(mmin, ans[tmp_step]));

         if(ans[tmp_step] == )  ans[tmp_step] = mmin;

         else ans[tmp_step] = min(ans[tmp_step], mmin);

         for(int i = ; i < sz; i++)

         {

             int v = g[u][i];

             ///该处判断条件很重要,把走过的路做标记

             if(!vis[v] && step[v] == step[u]- && mmin == col[u][i])

             {

                 vis[v] = ;

                 q.push(v);

             }

         }

     }

     return ;

 }

 int main()

 {

     //===================input=====================

     while(~scanf("%d%d", &n, &m))

     {

         init();

         while(m--)

         {

             int a, b, c;

             scanf("%d%d%d", &a, &b, &c);

             if(a == b) continue;

             g[a].push_back(b);

             g[b].push_back(a);

             col[a].push_back(c);

             col[b].push_back(c);

         }

         //===============逆向bfs===============

         //============获得最短步数=============

         bfs1();

         //===============正向bfs===============

         //==========获得每步的走廊颜色=========

         bfs2();

         printf("%d\n", step[]);

         for(int i = ; i < step[]; i++)

         {

             if(i) printf(" ");

             printf("%d", ans[i]);

         }

         printf("\n");

     }

     return ;

 }