#include <fstream>
#include <set>
#include <vector>

#define MAXNODES 50000
#define INF 1 << 30

using namespace std;

ifstream in( "dijkstra.in" );
ofstream out( "dijkstra.out" );

vector<pair<int, int>> v[ MAXNODES + 1 ];
set<pair<int, int>> myset;
int costs[ MAXNODES + 1 ];

int n, m;

void dijkstra( )
{
    myset.insert( make_pair( 0, 1 ) );
    while( myset.empty( ) == false )
    {
        int currentnode = myset.begin( )->second;
        int currentdist = myset.begin( )->first;
        myset.erase( myset.begin( ) );

        for( int i = 0; i < v[ currentnode ].size( ); i++ )
        {
            int no = v[ currentnode ][ i ].second;
            int d = v[ currentnode ][ i ].first;
            if( costs[ no ] > costs[ currentnode ] + d )
            {
                if( costs[ no ] != INF )
                    myset.erase( myset.find( make_pair( costs[ no ], no ) ) );
                costs[ no ] = costs[ currentnode ] + d;
                myset.insert( make_pair( costs[ no ], no ) );
            }
        }
    }
}

void read( )
{
    in >> n >> m;

    int a, b, cost;
    for( int i = 1; i <= m; i++ )
    {
        in >> a >> b >> cost;
        v[ a ].push_back( make_pair( cost, b ) );
    }
    for( int i = 2; i <= n; i++ )
    {
        costs[ i ] = INF;
    }
}

void print( )
{
    for( int i = 2; i <= n; i++ )
    {
        if( costs[ i ] != INF )
        out << costs[ i ] << " ";
        else
        {
            out << 0 << " ";
        }
    }
}

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