#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

list< pair< int , int > > G[ 50010 ];
int i,j,n,m,ans[50010],use[ 50010 ],x,y,c;
priority_queue< pair< int ,int > , vector< pair< int ,int > > , greater< pair< int , int > > > pq;

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y>>c;
        G[ x ].push_back( { y , c } );
    }

    pq.push( { 0 , 1 } );
    while( pq.size() )
    {
        use[ pq.top().s ] = 1;
        ans[ pq.top().s ] = pq.top().f;

        for( auto it : G[ pq.top().s ] )
            if( !use[ it.f ] )
                pq.push( { pq.top().f + it.s , it.f } );

        while( pq.size() && use[ pq.top().s ] ) pq.pop();
    }

    for( i = 2 ; i <= n ; i++ )
        fout<<ans[ i ]<<' ';

return 0;
}