#include<stdio.h>

#define nmax 50001
#define inf 0x3f3f3f

struct nod
{
    int drum,cost;
    nod *urm;
} *l[nmax];

struct heap
{
    int dr,poz;
}h[nmax];

int n,m,sol[nmax],lh[nmax],viz[nmax];

void add(nod *&,int,int);
void dijkstra();
void sift(int,int);
void percolate(int);
void swap(int,int);

int main()
{
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(l[a],b,c);
        }
    
    dijkstra();
    
    for(int i=2;i<=n;++i)
        if (sol[i]==inf)
            printf("0 ");
        else
            printf("%d ",sol[i]);
    printf("\n");
    return 0;
}

void add(nod *&inc,int info1,int info2)
{
    nod *p=new nod;
    p->drum=info1;
    p->cost=info2;
    p->urm=inc;
    inc=p;
}

void sift(int k,int n2)
{
    int fiu=1;
    while (fiu)
    {
        fiu=0;
        if (2*k <= n2)
            {
            fiu=2*k;
            if (2*k+1 <= n2 && h[fiu].dr < h[2*k+1].dr)
                fiu=2*k+1;
                
            if (h[fiu].dr < h[k].dr)
                fiu=0;
            }
        
        if (fiu)
            {
            swap(fiu,k);
            k=fiu;
            }
    }
}

void percolate(int k)
{
    while (k/2>0 && h[k/2].dr > h[k].dr)
        {
            swap(k/2,k);
            k=k/2;
        }
}

void swap(int a,int b)
{
    heap aux=h[a];
    h[a]=h[b];
    h[b]=aux;
    
    lh[h[a].poz]=a;
    lh[h[b].poz]=b;
}

void dijkstra()
{
    int nlate=n;
    
    for(int i=1;i<=n;++i)
        {
        h[i].poz=i;
        lh[i]=i;
        sol[i]=inf;
        h[i].dr=inf;
        }
    
    sol[1]=0;
    h[1].dr=0;
        
    for(int j=1;j<=n;j++)
        {
            int pmin=h[1].poz;
            swap(1,nlate--);
            sift(1,nlate);
            
            nod *t=l[pmin];
            
            while (t)
            {
                if (sol[t->drum] > sol[pmin]+t->cost )
                    {
                    sol[t->drum] = sol[pmin]+t->cost;
                    h[ lh[t->drum] ].dr= sol[t->drum];
                    percolate(lh[t->drum]);
                    }
                
                t=t->urm;
            }
        }
}