#include<iostream>
#include<fstream>
using namespace std;
float a[5000][5000],d[5000],mini;
int s[5000],t[5000],n,i,j,S,poz,r,m;
float Pinfinit=1.e20;
void citire(float a[5000][5000],int &n,int &m)
{
    ifstream f("dijkstra.in");
    float c;
    int i,j;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i==j) a[i][j]=0;
        else a[i][j]=Pinfinit;
    while(f>>i>>j>>c)
    a[i][j]=c;}

    void drum (int i)
    {
        if(t[i]) drum (t[i]);
        cout<<i<<" ";
    }
int main()
{ ofstream g("dijkstra.out");
    citire(a,n,m);
    r=1;
    s[r]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=a[r][i];
        if(i!=r) if(d[i]<Pinfinit) t[i]=r;}

        for(i=1;i<=n;i++)
        {
            mini=Pinfinit;
            for(j=1;j<=n;j++)
                if(s[j]==0)
                if(d[j]<mini)
            {
                mini=d[j];
                poz=j;}
                s[poz]=1;
                for(j=1;j<=n;j++)
                    if(s[j]==0)
                if(d[j]>d[poz]+a[poz][j])
                {
                    d[j]=d[poz]+a[poz][j];
                    t[j]=poz;
                }}
                for(i=1;i<=n;i++)
                    if(i!=r)
                    if(t[i]) g<<i<<" ";
                }