#include<stdio.h>
#define Nmax 50010
#define Inf 1<<30
 
int n,m,h[Nmax],poz[Nmax],best[Nmax],i,cst,x,y,k;
struct graf {int inf,cost; graf *adr;} *v[Nmax];
 
 
void add(int i, int j, int cst)
{
    graf *c;
    c=new graf;
     
    c->inf=j;
    c->cost=cst;
    c->adr=v[i];
    v[i]=c;
}
 
void swap(int i, int j)
{
    int aux;
     
    poz[h[i]]=j; 
    poz[h[j]]=i; 
     
    aux=h[i]; h[i]=h[j]; h[j]=aux;
     
}
 
int pozmin(int i)
{
    if(2*i+1<=k)
         
        if( best[ h[2*i+1] ] < best[ h[2*i] ] ) return 2*i+1;
     
    return 2*i;
}
 
 
void down(int i)
{
    int p;
     
    if(i<=k/2)
    {
        p=pozmin(i);
         
        if(best[h[i]] > best[h[p]]) 
        {
            swap(i,p);
            down(p);
        }
    }
}
 
void up(int i)
{
    if(i>1)
    {
        if(best[h[i]]<best[h[i>>1]])
        {
            swap(i,i>>1);
            up(i>>1);
        }
    }
}
 
void dijkstra()
{
    int i;  
    for(i=2;i<=n;i++)
    {
        best[i]=Inf;
        poz[i]=-1;
    }
    poz[1]=1; 
    h[++k]=1;
     
    while(k)
    {
        int nod=h[1];
        swap(1,k);
        poz[h[1]]=1;
        k--;
        down(1);
         
        graf *c;
             
        for(c=v[nod];c;c=c->adr)
        {
            if( best[c->inf] > best[nod] + c->cost)
            {
                best[c->inf]=best[nod]+c->cost;
                 
                if(poz[c->inf]==-1) { h[++k]=c->inf; poz[c->inf]=k; up(k);}
                else up(poz[c->inf]);
            }
        }
    }
}
 
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
     
    scanf("%d %d",&n,&m);
     
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&cst);
         
        add(x,y,cst);
    }
     
    dijkstra();
     
    for(i=2;i<=n;i++)
    {
        if(best[i]==Inf) printf("0 ");
        else printf("%d ",best[i]);
    }
     
    return 0;
}