#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

struct point { int v,c; point *l; } *G[50001],*p;
int D[50001],H[50001],P[50001],n,m,h;

void read_data ()
{
    int i,x,y,c;
    freopen ( "dijkstra.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    for ( i=0 ; i<m ; i++ )
    {
        scanf ( "%d %d %d" , &x , &y , &c );
        p = new point;
        p->l = G[x];
        p->c=c;
        p->v = y;
        G[x]=p;
    }
    fclose ( stdin );
}

void write_data ()
{
    int i;
    freopen ( "dijkstra.out " , "w" , stdout );
    for ( i=2 ; i<n ; i++ ) printf ( "%d " , (D[i]!=INF)?(D[i]):0 );
    printf ( "%d\n" , (D[n]!=INF)?(D[i]):0 );
    fclose ( stdout );
}

void swap ( int x , int y )
{
    int t = H[x]; H[x]=H[y] ; H[y]=t;
    P[H[x]]=x; P[H[y]]=y;
}

void heap_up ( int x )
{
    for ( ; x && D[H[x]] < D[H[x/2]] ; x/=2 )
        swap ( x , x/2 );
}

void push_H (int x)
{
    H[++h]=x; P[x]=h;
    heap_up ( h );
}

void drown ( int x )
{
    int st,dr,i;
    if ( x*2+1<=h )
    {
        st=H[2*x+1];
        if ( 2*x+2 <=h ) dr = H[2*x+2]; else dr=st-1;
        if (st>dr) i=x*2+1; else i=x*2+2;
        if (D[H[x]]>D[H[i]])
        {
            swap ( x , i );
            drown ( i );
        }
    }
}

int pop_H ()
{
    swap (0 , h); h--;
    drown ( 0 );
    return H[h+1];
}

int main ()
{
    int i,v;
    read_data ();
    memset ( D , INF , (n+2) * (sizeof ( int )) );h=-1;
    D[1]=0;
    push_H (1);
    while ( h>=0 )
    {
        v = pop_H ();H[h+1]=0;
        for ( p=G[v] ; p ; p=p->l )
        {
            if ( D[p->v] == INF )
            {
                D[p->v] = D[v]+p->c;
                push_H ( p->v );
            }
            if ( D[p->v] > D[v]+p->c )
            {
                D[p->v] = D[v]+p->c;
                heap_up ( P[p->v] );
            }
        }
    }
    write_data ();
    return 0;
}