#include <set>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#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;
set< pr > Q;
vector< vector< pr > > v;
vector< pr >::const_iterator it, iend;
set< pr >::iterator itmm;
int main()
{pr vertex;
 u n, m, i, x, y, c;
	ifstream in("dijkstra.in");
	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 ) );
	}
	d.resize(n); 
	d.assign( n, inf ); 
	Q.insert( mk( 0, 0 ) ); 
	while( !Q.empty() )
	{itmm=Q.begin();
		vertex=*itmm; 
		Q.erase(itmm); 
		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.insert( mk( d[ it->first ], it->first ) );
	}
	replace( d.begin(), d.end(), inf, 0 );
	ofstream out( "dijkstra.out" );
	copy( d.begin()+1, d.end(), ostream_iterator<u>(out, " ") );
	return 0;
}