# include <fstream>
# include <vector>
# include <queue>
# include <algorithm>

using namespace std;

const int maxn = 51000;
const int inf = 0x3f3f3f3f;
int n, m;
vector < pair <int, int> > G[maxn];
int dist [ maxn ];//, from [ maxn ];
bool viz [ maxn ];

priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > h;



void build_graph (){
	
	int i, x, y, c;
	ifstream f ( "dijkstra.in" );
	
	f >> n >> m;
	for ( i = 0; i < m; ++ i ){
		f >> x >> y >> c;
		G [ x ] . push_back ( make_pair(c, y) );
	}
	
	f . close ();
	
}

void Dijkstra(){
	
	int minim;
	vector < pair <int, int> > :: iterator it;
	
	//init
	//for ( i = 2; i <= n; ++ i ){
		//dist [ i ] = inf;
		//from [ i ] = -1;
	//}
	memset(dist, 0x3f, 4*(n+2));
	dist [ 1 ] = 0;
	//from [ 1 ] = 0;
	h . push ( make_pair( 0 , 1 ) );
	
	//relax
	while ( ! h . empty() ){
		minim = h . top () . second;
		h . pop();
		if ( viz [ minim ] )	continue;
		viz [ minim ] = true;
		for ( it = G[minim].begin(); it != G [ minim ]. end (); ++ it )
			if ( dist [ minim ] + it->first < dist [ it->second ] ){
				dist [ it->second ] = dist [ minim ] + it->first;
				//from [ G [ minim ] [ i ] ] = minim;
				h . push ( make_pair( dist [ it->second ], it->second ) );
			}
	}
	
}

void afis (){
	
	ofstream g ( "dijkstra.out" );
	int i;
	
	for ( i = 2; i <= n; ++ i )
		if ( dist [ i ] != inf )
			g << dist [ i ] << ' ';
		else g << "0 ";
	g << '\n';
	
	g . close ();
	
}

int main (){
	
	build_graph ();
	Dijkstra ();
	afis ();
	
	return 0;
	
}