dsa

#include <bits/stdc++.h>
using namespace std;
int n,k,a,b,c;
vector <int> v[100002];
vector <int> w[100002];
pair<int,int> f[100002];
vector <int> l;
int t[100002];

    int main() {
cin>>n>>k;
for(int i=0;k>i;i++)
{
    cin>>a>>b>>c;
    v[a].push_back(b);
    w[a].push_back(c);
    v[b].push_back(a);
    w[b].push_back(c);
}
priority_queue <pair<int,int >  ,vector <pair <int,int> > ,greater <pair<int,int > > >q;
q.push({0,1});
for(int r=2;n>=r;r++)
{
    f[r].first=100000000;
}
t[1]=0;

while(!q.empty())
{
    int x=q.top().first;
    int y=q.top().second;

    q.pop();
    if(t[y])
        continue;

    t[y]=x;
    for(int i=0;v[y].size()>i;i++)
    {
        if(t[v[y][i]]==0 and v[y][i]!=1 and t[y]+w[y][i]<f[v[y][i]].first)
            {q.push({t[y]+w[y][i],v[y][i]});f[v[y][i]].first=t[y]+w[y][i];f[v[y][i]].second=y;}
    }
}
l.push_back(n);
int m=n;
while(f[m].second!=0)
{
    l.push_back(f[m].second);
    m=f[m].second;
}
sort(l.begin(),l.end());
for(int i=0;l.size()>i;i++)
    cout<<l[i]<<endl;


    }