#include <cstdio>
#include <vector>
#define t(x) (x) / 2
#define fs(x) (x) * 2
#define fd(x) (x) * 2 + 1

using namespace std;

const int MAX_N = 50002 ;
const int INF = 1 << 30 ;
const int PARS = 10000 ;

vector < pair< int, int > > edge[ MAX_N ];

int heap[ MAX_N ], cost[ MAX_N ], pos[ MAX_N ];
int N, M, heapSize, poz = PARS - 1;
char buff[ PARS ];

void read_const( int &x)
{
    x = 0;
    while( buff[ poz ] < '0' || buff[ poz ] > '9' )
        if( ++poz == PARS )
        {
            fread( buff, 1, PARS, stdin);
            poz = 0;
        }

    while( '0' <= buff[ poz ] && buff[ poz ] <= '9' )
    {
        x = x * 10 + buff[ poz ] - '0';
        if( ++poz == PARS )
        {
            fread( buff, 1, PARS, stdin );
            poz = 0;
        }
     }
}


void read()
{
    int i, x, y, c;
    freopen("dijkstra.in","r",stdin);
    read_const( N );
    read_const( M );
    for( i = 1; i <= M; ++i )
    {
        read_const( x );
        read_const( y );
        read_const( c );
        edge[ x ].push_back( make_pair( y, c ) );
    }
    fclose(stdin);
}

void initial()
{
    int i;
    for( i = 2; i <= N; ++i )
        pos[ i ] = -1, cost[ i ] = INF;
}

void swap( int x, int y )
{
    int aux = heap[ x ];
    heap[ x ] = heap[ y ];
    heap[ y ] = aux;
}

void up_heap( int node )
{
    while( node > 1 && cost[ heap[ node ] ] < cost[ heap[ t( node ) ] ] )
    {
        pos[ heap[ node ] ] = t( node );
        pos[ heap [ t( node ) ] ] = node;
        swap( node, t( node ) );
        node = t( node );
    }
}

void down_heap( int node )
{
    while( ( fs( node ) <= heapSize && cost[ heap[ node ] ] > cost[ heap [ fs( node ) ] ] )  ||
            ( fd( node ) <= heapSize && cost[ heap[ node ] ] > cost[ heap [ fd( node ) ] ] ) )
            if( fd( node ) <= heapSize )
            {
                if( cost[ heap [ fs( node ) ] ] < cost[ heap [ fd( node ) ] ] )
                {
                    swap( node, fs( node ) );
                    pos[ heap[ node ] ] = node;
                    pos[ heap [ fs( node ) ] ] = fs( node );
                    node = fs( node );
                }
                else
                {
                    swap( node, fd( node ) );
                    pos[ heap[ node ] ] = node;
                    pos[ heap [ fd( node ) ] ] = fd( node );
                    node = fd( node );
                }
            }
            else
            {
                swap( node, fs( node ) );
                pos[ heap[ node ] ] = node;
                pos[ heap [ fs( node ) ] ] = fs( node );
                node = fs( node );
            }

}

void dijkstra()
{
    int i, min, node, costEdge;

    initial();

    heap[ ++heapSize ] = 1;
    pos[ 1 ] = 1;

    while( heapSize )
    {
        min = heap[ 1 ];
        swap( 1, heapSize );
        pos[ heap[ 1 ] ] = 1;
        heapSize --;
        down_heap( 1 );

        for( i = 0; i < edge[ min ].size(); ++i )
        {
            node = edge[ min ][ i ].first;
            costEdge = edge[ min ][ i ].second;
            if( costEdge + cost[ min ] < cost[ node ] )
            {
                cost[ node ] = costEdge + cost[ min ];
                if( pos[ node ] != -1 )
                    up_heap( pos[ node ] );
                else
                {
                    heap[ ++heapSize ] = node;
                    pos[ node ] = heapSize;
                    up_heap( heapSize );
                }
            }
        }
    }
}

void write()
{
    int i;
    freopen("dijkstra.out","w",stdout);
    for( i = 2; i <= N; ++i )
        printf("%d ", cost[ i ] == INF ? 0 : cost[ i ] );
    fclose(stdout);
}

int main()
{
    read();
    dijkstra();
    write();
    return 0;
}