#include <iostream>
#include <fstream>
#define pinf 100000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M,Start[50010],T[3][500010],D[50010],ant[50010],viz[50010];
void init()
{
    int i;
    D[1]=0;
    for(i=2; i<=N; i++)
    {
        D[i]=pinf;
    }
}
void citire()
{
    int i,x,y,c;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y>>c;
        T[0][i]=y;
        T[1][i]=Start[x];
        T[2][i]=c;
        Start[x]=i;
    }
}
void djikstra(int nod)
{
    int i,j,p,poz,minn=0;
    while(minn!=pinf)
    {
        minn=pinf;
        for(j=2; j<=N; j++)
        {
            if(viz[j]==0)
            {
                if(D[j]<minn)
                {
                    poz=j;
                    minn=D[j];
                }
            }
        }
        if(minn!=pinf)
        {
            viz[poz]=1;
            p=Start[poz];

            while(p!=0)
            {
                if(D[T[0][p]]>D[poz]+T[2][p])
                {
                    D[T[0][p]]=D[poz]+T[2][p];
                    ant[T[0][p]]=poz;
                }
                p=T[1][p];
            }
        }
    }
}
void afisare()
{
    int i;
    for(i=2; i<=N; i++)
    {
        fout<<D[i]<<' ';
    }

}
int main()
{
    int S,i,p;
    fin>>N>>M;
    citire();
    init();
    p=Start[1];
    while(p!=0)
    {
        D[T[0][p]]=T[2][p];
        ant[T[0][p]]=1;
        p=T[1][p];
    }
    viz[1]=1;
    djikstra(1);
    afisare();
}