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


using namespace std;
int lHeap;
int d[N_MAX], H[N_MAX], P[N_MAX];
vector< pair< int, int > > G[N_MAX];
vector< pair< int, int > >::const_iterator it, iend;
void DownHeap( int k )
{
    for( int son=k<<1; son <= lHeap; k=son, son<<=1 )
    {
        if( son < lHeap && d[H[son]] > d[H[son+1]] )
            ++son;
        if( d[H[k]] <= d[H[son]] )
            return;
        swap( H[k], H[son] );
        P[H[k]]=k;
        P[H[son]]=son;
    }
}
void UpHeap( int k )
{
    for( int key=d[H[k]], f=k>>1; k > 1 && d[H[f]] > key; k=f, f>>=1 )
    {
        swap( H[k], H[f] );
        P[H[k]]=k;
        P[H[f]]=f;
    }
}
inline int pop()
{
    int r=H[1];
    P[H[1]]=-1;
    H[1]=H[lHeap];
    P[H[1]]=1;
    --lHeap;
    DownHeap( 1 );
    return r;
}
inline void push( int k )
{
    H[++lHeap]=k;
    P[k]=lHeap;
    UpHeap( lHeap );
}
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 ) );
    }
    push( 1 );
    while( lHeap )
    {
        x=pop();
        for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
        {
            if( 0 == P[it->first] )
            {
                d[it->first]=d[x]+it->second;
                push( it->first );
            }
            else if( d[it->first] > d[x]+it->second )
                  {
                      d[it->first]=d[x]+it->second;
                      UpHeap( P[it->first] );
                  }
        }
    }
    ofstream out( "dijkstra.out" );
    copy( d+2, d+N+1, ostream_iterator<int>(out, " ") );
    out<<'\n';
    return EXIT_SUCCESS;
}