#include <fstream>
#include <queue>
#include <vector>

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

#define f first
#define s second
#define NMAX 50005
#define INF ( ( 1 << 30 ) - 1 )

vector< pair< int, int > >G[ NMAX ];
///G vector< pair< int, int > >[ 50005 ]
///G[ x ] vector< pair< int, int > >
///G[ x ][ 1 ] pair< int, int >
priority_queue< pair< int,int >, vector< pair< int, int >>, greater< pair< int, int >> >q;
pair< int, int >nod;

int viz[ NMAX ], N, M, x, y, c, i, d[ NMAX ];

int main ()
{
    fin>> N >> M;
    for( i = 1; i <= M; i++ )
    {
        fin >> x >> y >> c;
        G[ x ].push_back( make_pair( c, y ) );
    }
    for( i = 2; i <= N; i++ )
        d[ i ] = INF;
    q.push( make_pair( 0, 1 ) );
    while ( q.size() )
    {
        nod = q.top();
        if ( viz[ nod.s ] == 0 )
        {
            viz[ nod.s ] = 1;
            for ( auto it:G[ nod.s ] )
            {
                if ( viz[ it.s ] == 0 )
                {
                    if ( d[ nod.s ] + it.f < d[ it.s ] )
                        d[ it.s ] = d[ nod.s ] + it.f;
                    q.push( make_pair( d[ nod.s ] + it.f, it.s ) );
                }
            }
        }
        q.pop();
    }
    for ( i = 2; i <= N; i++ )
    {
        if ( d[ i ] == INF )
            fout<< 0 << ' ';
        else
            fout<< d[ i ] << ' ';
    }
}