/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 29, 2010, 12:49 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#define Nmax 50010
#define inf 0x3f3f3f3f
#define mk make_pair< unsigned int, unsigned int >

/*
 *
 */
using namespace std;
typedef pair< int, int > pr;
int N;
int v[Nmax], position[Nmax];
vector< int > dist;
vector< vector< pr > > Graph;
vector< pr >::const_iterator it, iend;
void sift( int k )
{
    int son;
    while( true )
    {
        son=2*k;
        if( son > N )
            break;
        if( 2*k+1 <= N && dist[v[son]] > dist[v[2*k+1]] )
            son=2*k+1;
        swap( v[k], v[son] );
        position[v[k]]=k;
        position[v[son]]=son;
        k=son;
    }
}
void percolate( int k )
{
    int key=v[k], f=k/2;
    while( k > 1 && dist[key] < dist[v[f]] )
    {
        swap( v[k], v[f] );
        position[v[k]]=k;
        position[v[f]]=f;
        k=f;
        f/=2;
    }
}
int main()
{int n, m, x, y, c, vertex;
    ifstream in("dijkstra.in");
    in>>n>>m;
    Graph.resize(n);
    dist.resize(n);
    while( m-- )
    {
        in>>x>>y>>c;
        x-=1;
        y-=1;
        Graph[x].push_back( mk( y, c ) );
    }
    dist[0]=0;
    v[++N]=0;
    position[0]=1;
    while( N )
    {
        vertex=v[1];
        v[1]=v[N];
        --N;
        sift( 1 );
        for( it=Graph[vertex].begin(), iend=Graph[vertex].end(); it < iend; ++it )
        {
            if( !position[it->first] || dist[it->first] > dist[vertex]+it->second  )
            {dist[it->first]=dist[vertex]+it->second;
                if( !position[it->first] )
                {
                    v[++N]=it->first;
                    position[N]=N;
                    percolate( N );
                }
                else percolate( position[it->first] );
            }
        }
    }
    ofstream out("dijkstra.out");
    copy( dist.begin()+1, dist.end(), ostream_iterator<int>(out, " ") );
    return 0;
}