#include<stdio.h>
#define INF 1000001
#define Nmx 50002


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

int n,m,viz[Nmx],Heap[Nmx*70],nr,cost[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;
}

int schimb(int x,int y)
{
    int aux=Heap[x];
    Heap[x]=Heap[y];
    Heap[y]=aux;
}

void up_heap(int k)
{
    while(k>1)
    {
        if(cost[Heap[k/2]]<=cost[Heap[k]])
            return ;
        viz[Heap[k/2]]=k;
        viz[Heap[k]]=k/2;
        schimb(k,k/2);
        k=k/2;
    }
}

void down_heap(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr&&cost[Heap[p+1]]<cost[Heap[p]])
            p++;
        if(cost[Heap[p]]>=cost[Heap[k]])
            return ;
        viz[Heap[p]]=k;
        viz[Heap[k]]=p;
        schimb(k,p);
        k=p;
    }
}

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

void solve()
{
    for(int i=2;i<=n;++i)
        cost[i]=INF;
    viz[1]=1;
    Heap[++nr]=1;
    while(nr)
    {
        int min=Heap[1];
        schimb(1,nr);
        viz[Heap[nr]]=0;
        Heap[nr--]=0;
        if(nr) viz[Heap[1]]=1;
        down_heap(1);
        for(nod *p=G[min];p;p=p->urm)
            if(cost[p->inf]>cost[min]+p->cost)
            {
                cost[p->inf]=cost[min]+p->cost;
                if(!viz[p->inf])
                {
                    Heap[++nr]=p->inf;
                    viz[p->inf]=nr;
                    up_heap(nr);
                }
                else up_heap(viz[p->inf]);
            }
    }
    for(int i=2;i<=n;++i)
        if(cost[i]!=INF)    printf("%d ",cost[i]);
        else printf("0 ");
    printf("\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    solve();
    return 0;
}