#include<stdio.h>
#define Nmx 50003
#define INF 100000001

int n,m,Heap[Nmx],nr,viz[Nmx],C[Nmx];
struct nod
{
    int inf,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 swap(int x,int y)
{
    int aux=Heap[x];
    Heap[x]=Heap[y];
    Heap[y]=aux;
}

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 in_jos(int k)
{
    while(2*k<=nr)
    {
        int min=C[Heap[2*k]],pz=2*k;
        if(2*k+1<=nr)
            if(C[Heap[2*k+1]]<min)
                min=C[Heap[2*k+1]],pz++;
        if(min<C[Heap[k]])
        {
            viz[Heap[k]]=pz;
            viz[Heap[pz]]=k;
            swap(k,pz);
            k=pz;
        }
        else break;
    }
}

void in_sus(int k)
{
    while(k/2>=1)
    {
        if(C[Heap[k/2]]>C[Heap[k]])
        {
            viz[Heap[k/2]]=k;
            viz[Heap[k]]=k/2;
            swap;
            k=k/2;
        }
        else break;
    }
}

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

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