/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 29, 2010, 12:49 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#define Nmax 50001
#define inf 0x3f3f3f3f
#define mk make_pair< int, 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;
inline void swap( int x, int y )
{
    x+=y;
    y=x-y;
    x-=y;
}
void sift( int k )
{
    int son;
    while( true )
    {
        son=2*k;
        if( son > N )
            break;
        if( 2*k < N && dist[v[2*k+1]] < dist[v[son]] )
            son=2*k+1;
        if( dist[v[son]] <= dist[v[k]] )
            break;
        swap( position[v[son]], position[v[k]] );
        swap( v[son], v[k] );
        k=son;
    }
}
void percolate( int k )
{
    int key=v[k], f=k/2;
    while( k > 1 && dist[key] > dist[v[f]] )
    {
        swap( position[v[k]], position[v[f]] );
        swap( v[k], v[f] );
        k=f;
        f=k/2;
    }
}
int main()
{bool ok;
    int n, m, x, y, c, vertex;
    ifstream in("dijkstra.in");
    in>>n>>m;
    Graph.resize(n);
    dist.resize(n);
    dist.assign( n, inf );
    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]=N;
    while( N )
    {
        vertex=v[1];
        v[1]=v[N];
        --N;
        sift( 1 );
        for( it=Graph[vertex].begin(), iend=Graph[vertex].end(); it < iend; ++it )
        {ok=false;
            if( inf == dist[it->first] )
                ok=true;
            if( dist[it->first] > dist[vertex]+ it->second )
            {
                dist[it->first]=dist[vertex]+it->second;
                if( ok )
                {
                    v[++N]=it->first;
                    position[N]=N;
                    percolate( N );
                }
                else sift( position[it->first] );
            }
        }
    }
    ofstream out("dijkstra.out");
    for( x=1; x < n; ++x )
        if( inf == dist[x] )
            out<<"0 ";
        else out<<dist[x]<<' ';
    return 0;
}