/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 29, 2010, 12:49 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#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+1 <= N && dist[v[son]] < dist[v[2*k+1]] )
            son=2*k+1;
        if( dist[v[son]] <= dist[v[k]] )
            break;
        swap( v[son], v[k] );
        position[v[son]]=son;
        position[v[k]]=k;
        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()
{bool ok;
 int n, m, x, y, c, vertex, i;
    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;
    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, percolate( N );
                else sift( position[it->first] );
            }
        }
    }
    ofstream out("dijkstra.out");
    for( i=1; i < n; ++i )
        if( inf == dist[i] )
            out<<"0 ";
        else out<<dist[i]<<' ';
    return 0;
}