#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011
#define oo 1<<28


using namespace std;
int d[N_MAX];
priority_queue< pair< int, int > > pQ;
vector< pair< int, int > > G[N_MAX];
vector< pair< int, int > >::const_iterator it, iend;
int main( void )
{
    int N, M, x, y, c;
    ifstream in( "dijkstra.in" );
    for( in>>N>>M; M; --M )
    {
        in>>x>>y>>c;
        G[x].push_back( pair< int, int >( y, c ) );
    }
    fill( d+2, d+N+1, oo );
    pQ.push( pair< int, int >( 0, 1 ) );
    for( y=1; y <= N && !pQ.empty(); ++y )
    {
        x=pQ.top().second; pQ.pop();
        for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
            if( d[it->first] > d[x]+it->second )
            {
                d[it->first]=d[x]+it->second;
                pQ.push( pair< int, int >( -d[it->first], it->first ) );
            }
    }
    ofstream out( "dijkstra.out" );
    copy( d+2, d+N+1, ostream_iterator<int>(out, " ") );
    out<<'\n';
    return EXIT_SUCCESS;
}