#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e5+5,M=2e5+5;
int n,m,x[M],y[M],z[M];
vector<pii> e[N];
int diss[N],dist[N],d[N];
void adde(int x,int y,int z){
    e[x].emplace_back(y,z);
}
int f[N],g[N],pf[N],pg[N],nu,nv;
bool fl;
int pre[N];
bool vis[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x[i]>>y[i]>>z[i];
        adde(x[i],y[i],z[i]),adde(y[i],x[i],z[i]);
    }
    queue<int> q;
    q.push(1);
    diss[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto &[v,w]:e[u]){
            if(!diss[v])diss[v]=diss[u]+1,q.push(v);
        }
    }
    q.push(n);
    dist[n]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto &[v,w]:e[u]){
            if(!dist[v])dist[v]=dist[u]+1,q.push(v);
        }
    }
    cout<<diss[n]-1<<'\n';
    for(int i=1;i<=n;++i)e[i].clear();
    for(int i=1;i<=m;++i){
        if(diss[x[i]]+dist[y[i]]==diss[n])adde(x[i],y[i],z[i]),++d[y[i]];
        if(diss[y[i]]+dist[x[i]]==diss[n])adde(y[i],x[i],z[i]),++d[x[i]];
    }
    for(int i=2;i<=n;++i)f[i]=1e9,g[i]=-1e9;
    for(auto &[v,w]:e[1])f[v]=g[v]=w,pf[v]=pg[v]=1,q.push(v),--d[v];
    int ans=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto &[v,w]:e[u]){
            if(w-f[u]>ans)ans=w-f[u],nu=u,nv=v,fl=0;
            if(g[u]-w>ans)ans=g[u]-w,nu=u,nv=v,fl=1;
            if(min(f[u],w)<f[v])f[v]=min(f[u],w),pf[v]=u;
            if(max(g[u],w)>g[v])g[v]=max(g[u],w),pg[v]=u;
            if(!--d[v])q.push(v);
        }
    }
    vector<int> ansl,ansr;
    ansl.push_back(nu);
    if(!fl){
        while(nu!=1)nu=pf[nu],ansl.push_back(nu);
    }
    else{
        while(nu!=1)nu=pg[nu],ansl.push_back(nu);
    }
    ansr.push_back(n);
    q.push(nv);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto &[v,w]:e[u])if(!vis[v])q.push(v),pre[v]=u;
    }
    int nw=n;
    while(nw!=nv)nw=pre[nw],ansr.push_back(nw);
    for(int i=ansl.size()-1;i>=0;--i)cout<<ansl[i]<<' ';
    for(int i=ansr.size()-1;i>=0;--i)cout<<ansr[i]<<' ';
    cout<<'\n';
}