#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pu push_back
#define ll long long
typedef pair <ll,ll> ii;
const int N=1e6;
long long mod=1e9;
ll n,m,s,t,l,k;
ll a[N+1],b[N+1],ds[N+10],dt[N+10],fs[N+10],ft[N+10],pt[N+10],ps[N+10];
vector <ii> adj[N+1],edge[N+10];
ii c[N+10],d[N+10];
bool o[N+10];
pair <ll,ii> e[N+10],ed[N+10];
void bfss(){
    queue <int> q;
    q.push(1);
    for(int i=1;i<=n;i++) ds[i]=mod;
    ds[1]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto x:adj[u]){
            int v=x.fi;
            if(ds[v]>ds[u]+1){
                ds[v]=ds[u]+1;
                q.push(v);
            }
        }
    }
    }
void bfst(){
    queue <int> q;
    q.push(n);
    for(int i=1;i<=n;i++) dt[i]=mod;
    dt[n]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto x:adj[u]){
            int v=x.fi;
            if(dt[v]>dt[u]+1){
                dt[v]=dt[u]+1;
                q.push(v);
            }
        }
    }
    }
void distras(){
    priority_queue <pair<ll,ii> > pq;
    for(int i=1;i<=n;i++) {
    fs[i]=mod;
    }
    pq.push({-mod,{0,1}});
    while(pq.size()){
        int u=pq.top().se.se;
        ll du=pq.top().se.fi,col=pq.top().fi;
        col=-col;
        pq.pop();
        if( col>fs[u]) continue;
        for(auto x:adj[u]){
            ll v=x.fi,w2=x.se;
            if(min(col,w2)<fs[v] and du+1==ds[v]){
                ps[v]=u;
                fs[v]=min(col,w2);
                pq.push({-fs[v],{du+1,v} });
            }
        }
    }
    }
void distrat(){
   priority_queue <pair<ll,ii>  > pq;
    for(int i=1;i<=n;i++) {
    ft[i]=mod;
    }
    pq.push({-mod,{0,n}});
    while(pq.size()){
        int u=pq.top().se.se;
        ll du=pq.top().se.fi,col=pq.top().fi;
        col=-col;
        pq.pop();
        if( col>ft[u]) continue;
        for(auto x:adj[u]){
            ll v=x.fi,w2=x.se;
            if(min(col,w2)<ft[v] and du+1==dt[v]){
                pt[v]=u;
                ft[v]=min(col,w2);
                pq.push({-ft[v],{du+1,v} });
            }
        }
    }
    }
void tinh(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pu({v,w});
        adj[v].pu({u,w});
    }
    s=1;
    t=n;
    bfss();
    distras();
    bfst();
    distrat();
    ll cnt=0;
    ll ans=0;
    ll U=0,V=0;
    for (int u = 1; u <= n; ++u)
    {
        for (auto [v, w]: adj[u])
        {
            if (ds[u] + dt[v] + 1 == ds[n])
            {
                if(ans<w - min ({w, fs[u], ft[v]})){
                    U=u;
                    V=v;
                }
                ans = max (ans, w - min ({w, fs[u], ft[v]}));
            }
        }
    }
    cout<<ds[n]<<'\n';
    vector <int> id;
    while(U!=0){
        id.push_back(U);
        U=ps[U];
    }
    reverse(id.begin(),id.end());
    while(V!=0){
        id.push_back(V);
        V=pt[V];
    }
    for(auto v:id) cout<<v<<" ";
    }
int main(){
    //freopen("jday.inp","r",stdin);
    //freopen("jday.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;

}
//code của anh Nam đẹp trai nhất CHL