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

int n,m,Heap[Nmx],nr,viz[Nmx],C[Nmx];
struct nod
{
    int inf,cost;
    nod *urm;
};
nod *G[Nmx];

void schimba(int a,int b)
{
    int aux=Heap[a];
    Heap[a]=Heap[b];
    Heap[b]=aux;
}

void add(int x,int y,int c)
{
    nod *aux;
    aux=new nod;
    aux->urm=G[x];
    aux->inf=y;
    aux->cost=c;
    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 in_jos(int poz)
{
    while(poz<=nr)
    {
        if(poz*2>nr) return;
        int c=poz<<1;
        if(c+1<=nr)
             if(C[Heap[c+1]] < C[Heap[c]])
                 c++;
         if (C[Heap[poz]]<= C[Heap[c]])
             return;
         viz[Heap[poz]]=c;
         viz[Heap[c]]=poz;
         schimba(poz,c);
         poz=c;
    }
}

void in_sus(int poz)
{
    while (poz>1)
    {
        if (C[Heap[poz]]<C[Heap[poz/2]])
        {
            viz[Heap[poz]]=poz/2;
            viz[Heap[poz/2]]=poz;
            schimba(poz,poz/2);
            poz=poz/2;
        }
        else
            return ;
    }
}



void dijkstra()
{
    for(int i=1;i<=n;++i)
    {
        C[i]=INF;
        viz[i]=-1;
    }
    C[1]=0;
    Heap[1]=1;viz[1]=1;
    nr=1;
    int min;
    while(nr)
    {
        min=Heap[1];
        schimba(1,nr);
        Heap[nr--]=0;
        viz[Heap[1]]=1;
        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[p->inf]=nr;
                in_sus(nr);
             }
             else
               in_sus(viz[p->inf]);
          }
    }
}

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