#include <map>
#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;
multimap< u, u > Q;
vector< vector< pr > > v;
vector< pr >::const_iterator it, iend;
multimap< u, u >::iterator itmm;
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.insert( mk( 0, 0 ) ); //introduce the first vertex
	while( !Q.empty() )
	{itmm=Q.begin();
		vertex=*itmm; //get the min vertex
		Q.erase(itmm); //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.insert( mk( d[ it->first ], it->first ) );
	}
	ofstream out( "dijkstra.out" );
	for( i=1; i < n; ++i )
		if( inf == d[i] )
			out<<"0 ";
	    else out<<d[i]<<' ';
	return 0;
}