#include <iostream>
#include <fstream>
//#define inf 10000
using namespace std;
ifstream in("date.in");
ofstream out("date.out");
int c[20][20],s[20],d[20],prec[20];
int n,m,vp,nrs,i,j,k;
int inf=10000;
void citire()
{
    int i,j,x,y,cs;

    for(i=1;i<=m;i++)
    {
        in>>x>>y>>cs;
        c[x][y]=cs;
    }
}
void initc()
{
    int i,j,k;
    for(i=1;i<=n;i++)
       {
            for(j=1;j<=n;j++)
                c[i][j]=inf;
        c[i][i]=0;
        }
}
void initvec()
{
    int i;
    d[0]=inf;
    for(i=1;i<=n;i++)
    {
        d[i]=c[vp][i];
        s[i]=0;
        if (c[vp][i]<inf)
            prec[i]=vp;
            else prec[i]=0;
    }
    s[vp]=1;
    prec[vp]=0;
}
void mini(int &k)
{
    k=0;
    int m=inf;
    int i;
    for(i=1;i<=n;i++)
        if((s[i]==0)&&(d[i]<m))
            {
                m=d[i];
                k=i;
            }
}
void drum(int l)
{
    if(l!=0)
    {
        drum(prec[l]);
        out<<l<<' ';
    }
    else out<<'\n';
}
int main()
{
    vp=1;
    in>>n>>m;
    initc();
    citire();
    initvec();
    int gata=0;
    while(!gata)
    {
        mini(k);
        if(k==0){ gata=1;
                    break;}
        nrs++;
        if((d[k]==inf)||(nrs==n)) gata=1;
            else
            {
                s[k]=1;
                for(j=1;j<=n;j++)
                    if((s[j]==0) && (d[j]>d[k]+c[k][j])&&(c[k][j]!=inf))
                            {
                                d[j]=d[k]+c[k][j];
                                prec[j]=k;
                            }
            }
    }
    /*for(i=1;i<=n;i++)
        {
            if(i!=vp)
                if(d[i]==inf) out<<" De la "<<vp<<" la "<<i<<" nu exista drum";
                else
                {
                    out<<" De la "<<vp<<" la "<<i<<" drumul minim este:"; drum(i);
                    out<<'\n';

                }
        }
        for(i=1;i<=n;i++)
        {for(j=1;j<=n;j++)
            cout<<c[i][j]<<" ";
            cout<<'\n';}*/
    for(i=2;i<=n;i++)
        out<<d[i]<<' ';
    in.close();
    out.close();
    return 0;
}