#include <iostream>
#include <fstream>
#define pinf 100000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M,Start[50010],D[50010],ant[50010],viz[50010],a[50010],poz1[50010],total,poz2[50010];
struct nod
{
    int info,cost;
    nod* urm;
};
nod *L[50010];
void init(int S)
{
    int i;
    for(i=1; i<=N; i++)
    {
        D[i]=pinf;
    }
    D[S]=0;
}
void citire()
{
    int i,x,y,c;
    nod *p;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y>>c;
        p=new nod;
        p->urm=L[x];
        p->info=y;
        p->cost=c;
        L[x]=p;

    }
}
void stergere(int i)
{
    if(2*i<=total)
    {
        if(a[2*i]<a[2*i+1])
        {
            a[i]=a[2*i];
            poz1[i]=poz1[2*i];
            poz2[poz1[i]]=i;
            stergere(2*i);
        }
        else
        {
            if(2*i+1<=total)
            {
                a[i]=a[2*i+1];
                poz1[i]=poz1[2*i+1];
                poz2[poz1[i]]=i;
                stergere(2*i+1);
            }
        }
    }
}
void schimbare(int i)
{
    int aux;
    if(i!=1)
    {
        if(a[i]<a[i/2])
        {
            aux=a[i];
            a[i]=a[i/2];
            a[i/2]=aux;
            aux=poz1[i];
            poz1[i]=poz1[i/2];
            poz1[i/2]=aux;
            poz2[poz1[i]]=i;
            poz2[poz1[i/2]]=i/2;
            schimbare(i/2);
        }
    }
}
void djikstra()
{
    int i,j,poz,minn=0;
    nod *p;
    while(minn!=pinf&&total!=0)
    {
        minn=a[1];
        poz=poz1[1];
        stergere(1);
        total--;
        if(minn!=pinf)
        {
            viz[poz]=1;
            p=L[poz];
            while(p!=NULL)
            {
                if(viz[p->info]==0)
                    if(D[p->info]>D[poz]+p->cost)
                    {
                        D[p->info]=D[poz]+p->cost;
                        a[poz2[p->info]]=D[p->info];
                        schimbare(poz2[p->info]);
                        ant[p->info]=poz;
                    }
                p=p->urm;
            }
        }
    }
}
void afisare(int S)
{
    int i;
    for(i=1; i<=N; i++)
    {
        if(i!=S)
        {
            if(D[i]!=pinf)
                fout<<D[i]<<' ';
            else
                fout<<0<<' ';
        }
    }

}
void construire()
{
    int i,aux;
    for(i=N/2; i>0; i--)
    {
        if(a[i]>a[i*2])
        {
            aux=a[i];
            a[i]=a[i*2];
            a[i*2]=aux;
            aux=poz1[i];
            poz1[i]=poz1[2*i];
            poz1[2*i]=aux;
            poz2[poz1[i]]=i;
            poz2[poz1[2*i]]=2*i;
        }
        if(a[i]>a[i*2+1]&&total>=2*i+1)
        {
            aux=a[i];
            a[i]=a[i*2+1];
            a[i*2+1]=aux;
            aux=poz1[i];
            poz1[i]=poz1[2*i+1];
            poz1[2*i+1]=aux;
            poz2[poz1[i]]=i;
            poz2[poz1[2*i+1]]=2*i+1;
        }
    }
}
int main()
{
    int i,S;
    nod *p;
    fin>>N>>M;
    S=1;
    citire();
    init(S);
    p=L[S];
    while(p!=NULL)
    {
        D[p->info]=p->cost;
        ant[p->info]=1;
        p=p->urm;
    }
    viz[S]=1;
    for(i=2; i<=N; i++)
    {
        a[i-1]=D[i];
        poz1[i-1]=i;
        poz2[i]=i-1;
    }
    total=N-1;
    construire();
    djikstra();
    afisare(S);
}