#include <queue>
#include <vector>
#include <fstream>
#include <iterator>
#define inf 0x3f3f3f3f
#define mk make_pair< unsigned int, unsigned int >

/*
 * 
 */
using namespace std;
typedef unsigned int u;
typedef pair< u, u > pr;
vector< u > d;
priority_queue< pr > Q;
vector< vector< pr > > v;
vector< pr >::const_iterator it, iend;
inline ostream& operator<<( ostream& out, u x )
{
	if( inf == x )
		out<<'0';
    else out<<(int)(x);
    return out;
} 
int main()
{pr vertex;
 u n, m, i, x, y, c;
	ifstream in("dijkstra.in");
	/*read data*/
	in>>n>>m;
	v.resize(n);
	for( i=0; i < m; ++i ) 
	{
		in>>x>>y>>c;
		x-=1;
		y-=1;
		v[x].push_back( mk( y, c ) );
	}
	/*stop*/
	d.resize(n); //allocate memmory
	d.assign( n, inf ); //intialize
	Q.push( mk( 0, 0 ) ); //introduce the first vertex
	while( !Q.empty() )
	{
		vertex=Q.top(); //get the min vertex
		Q.pop(); //exclude it
		for( it=v[vertex.second].begin(), iend=v[vertex.second].end(); it < iend; ++it )
			if( d[ it->first ]  > it->second+vertex.first )
			  d[ it->first ]=it->second+vertex.first, Q.push( mk( d[ it->first ], it->first ) );
	}
	ofstream out( "dijkstra.out" );
	copy( d.begin()+2, d.end(), ostream_iterator<u>( out, " " ) );
	return 0;
}