#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <vector <long> > c;
long n,d[50000],mini,pred[50000],viz[50000],x,m;//d e drumul minim de la vf de pornire la varful i
void citire ()
{
    //citim muchii si cost si le transformam in matrice de costuri
    long i,j,x,y,z;
    ifstream f("dijkstra.in");
    f>>n>>m;//numarul de noduri
    c.resize(n+1);
    for (i=1;i<=n;i++)
        c[i].resize(n+1);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i==j)
                c[i][j]=0;//pe diagonala principala initializam cu 0 matricea costurilor
            else
                c[i][j]=16000;//16000==infinit
    for (i=0;i<m;i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
        c[y][x]=z;//este graf neorientat si de aceea marcam si elementul c[y][x] cu costul muchiei
    }
}
void minim (long &k,long &mini)//finctia care va stabili minimul din vectorul d
{
    long i,j;mini=32000;
    for (i=1;i<n;i++)
        if (viz[i]==0&&d[i]<mini)
        {
            mini=d[i];
            k=i;
        }
}
void dijkstra()
{
    long i,j,k;
    x=1;//nodul de pornire
    for (i=1;i<=n;i++)
    {
        d[i]=c[x][i];//umplem vectorul d cu valori de pe linia corespunzatoare lui x din matricea costurilor
        pred[i]=x;//predecesorul fiecarui nod va fi nodul x(initial)
        viz[i]=0;
    }
    viz[x]=1;
    pred[x]=0;
    long ok=1,nr=1;//nr=numarul de noduri cu care se leaga
    while (nr<n&&ok)//cat timp nu a terminat nodurile si minimul e diferit de infinit
    {
        minim(k,mini);
        if (mini==16000)
            ok=0;
        else
        {
            viz[k]=1;//se marcheaza nodul care are costul minim
            for (i=1;i<=n;i++)//verificam daca de la nodul k putem crea drumuri de lungime minima catre restul de noduri nevizitate
                if (viz[i]==0&&mini+c[k][i]<d[i])
                {
                    d[i]=mini+c[k][i];
                    pred[i]=k;
                }
            nr++;
        }
    }

}
void afis (long x)
{
    if (x!=0)
        {
            afis(pred[x]);
            cout<<x<<" ";
        }
}
int main ()
{
    citire ();
    dijkstra();
    ofstream g ("dijkstra.out");
    for (long i=2;i<=n;i++)
        if (d[i]!=16000)
        {
            g<<d[i]<<" ";
        }
    g.close();
    return 0;
}