1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <vector> 5 #include<memory.h> 6 #include<algorithm>//reverse 7 using namespace std; 8 #define maxn 100002 9 #define INF 6510 struct node11 {12     int u;13     int w;14     node(long long x,long long y)15     {16         u = x;17         w = y;18     }19     bool operator < ( const node& p ) const20     {      return w > p.w;   }21 };22 vector<long long>g[maxn];23 vector<long long>cost[maxn];24 long long d[maxn];25 long long par[maxn];26 int dijk(int n)27 {28     memset(d, INF, sizeof(d));29     memset(par, -1, sizeof(par));30     priority_queue<node>q;31     q.push(node(1,0));32     d[1]=0;33     while(!q.empty())34     {35         node top = q.top();36         q.pop();37         int uu = top.u;38         if(uu == n) return d[n];39         for(int i = 0;i < g[uu].size(); i++)40         {41             int v = g[uu][i];42             if(d[uu] + cost[uu][i] < d[v])43             {44                 d[v] = d[uu] + cost[uu][i];45                 par[v] = uu;46                 q.push(node(v,d[v]));47             }48         }49     }50     return -1;51 }52 int main()53 {54     //freopen("input.txt","r",stdin);55     int n,e,u,v;56     long long w;57     cin>>n>>e;58     for(int i = 0; i < e; i++)59     {60         cin>>u>>v>>w;61         g[u].push_back(v);cost[u].push_back(w);62         g[v].push_back(u);cost[v].push_back(w);63 64     }65     w = dijk(n);66     if(w == -1) cout<<"-1"<<endl;67     else68     {69         int t = n;70         int s[maxn];71         int k = 0;72         while(t != -1)73         {74             s[k++] = t;75             t = par[t];76         }77         for(int j = k - 1; j >= 0; j--)78             cout<<s[j]<<" ";79         cout<<endl;80     }81 }