#include<cstdio>
#define INF 0x3f3f3f3f
#define Nmx 50001

using namespace std;

int n,m,C[Nmx],H[4*Nmx],nr,poz[4*Nmx];

struct nod
{
    int inf;
    int cost;
    nod *urm;
};
nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->cost=c;
    aux->urm=G[x];
    G[x]=aux;
}

void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
}

void up(int k)
{
    while(k>1&&C[H[k]]<C[H[k/2]])
    {
        int aux=H[k];
        H[k]=H[k/2];
        H[k/2]=aux;
        poz[H[k]]=k;
        poz[H[k/2]]=k/2;
        k=k/2;
    }
}

void down(int k)
{
    while(k*2<=nr)
    {
        int t=k*2;
        if(t+1<=nr&&C[H[t+1]]<C[H[t]])
            t++;
        int aux=H[t];
        H[t]=H[k];
        H[k]=aux;
        poz[H[t]]=t;
        poz[H[k]]=k;
        k=t;
    }
}

void dijkstra()
{
    for(int i=1;i<=n;++i)
    {
        C[i]=INF;
        poz[i]=-1;
    }
    C[1]=0;
    H[1]=1;poz[1]=1;
    nr=1;
    while(nr)
    {
        int x=H[1];
        poz[H[nr]]=1;
        poz[H[1]]=-1;
        H[1]=H[nr--];
        down(1);
        for(nod *p=G[x];p;p=p->urm)
            if(p->cost+C[x]<C[p->inf])
            {
                C[p->inf]=C[x]+p->cost;
                if(poz[p->inf]==-1)
                {
                    H[++nr]=p->inf;
                    poz[p->inf]=nr;
                    up(nr);
                }
                else up(poz[p->inf]);
            }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijlstra.out","w",stdout);
    citire();
    dijkstra();
    for(int i=2;i<=n;++i)
        if(C[i]==INF)
            printf("0 ");
        else printf("%d ",C[i]);
    printf("\n");
    return 0;
}