1 #include <iostream> 2 #include <string.h> 3 #include <queue> 4 #include <vector> 5 #include <utility> 6 #include <cstdio> 7 using namespace std; 8 #define N 100005 9 #define M 40000510 typedef long long LL;11 const LL inf = 1<<62;12 LL v[M],w[M],next[M],first[N],d[N],e;13 int f[N],o[N];14 bool inq[N];15 void addedge(int a,int b,int x){16     v[e]=b;17     w[e]=x;18     next[e]=first[a];19     first[a]=e++;20 }21 void SPFA(int st){22     queue<int> q;23     d[st]=0;24     q.push(st);25     inq[st]=1;26     f[1]=-1;27     while(!q.empty()){28         int u = q.front();29         q.pop();30         inq[u] = 0;31         for(int i=first[u];i!=-1;i=next[i]){32             if(d[v[i]]>d[u]+w[i]){33                 d[v[i]]=d[u]+w[i];34                 f[v[i]]=u;35                 if(!inq[v[i]]){36                     q.push(v[i]);37                     inq[v[i]]=1;38                 }39             }40         }41     }42 }43 int main(){44     int n,m,a,b,x;45    // freopen("test.txt","r",stdin);46     while(cin>>n>>m){47         e=0;48         for(int i=0;i<=n;i++){49             first[i]=-1;50             inq[i]=false;51             d[i]=inf;52         }53         for(int i=0;i<m;i++){54             cin>>a>>b>>x;55             addedge(a,b,x);56             addedge(b,a,x);57         }58         SPFA(1);59         if(d[n]==inf)cout<<"-1"<<endl;60         else {61             int r=0;62             for(int i=f[n];i!=-1;i=f[i]){63                 o[r]=i;64                 r++;65             }66             for(int i=r;i>0;i--){67                 printf("%d ",o[i-1]);68             }69             printf("%d\n",n);70         }71     }72     return 0;73 }