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

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

const int Dim = 50001;
using VI = vector < pair < int,  int > > ;
using VVI = vector < VI >;

VVI G;
priority_queue < pair < int , int >, vector< pair < int , int > >, greater < pair < int , int > >  > Q;


int n,m,d[Dim];

int main() {
	
	fin >> n;
	G = VVI ( n + 1 );
	int x,w,y;
	fin >> m;
	for ( ; m > 0; --m)  {
		
		fin >> x >> y >> w;
		G[x].push_back({y,w});
	}
	for(  int i = 1; i <= n; ++i)
		d[i] = 0x3f3f3f3f;
	Q.push({0,1});
	d[1] = 0;
	while ( !Q.empty() ) {
		int dx = Q.top().first;
		int x = Q.top().second;
		Q.pop();
		if ( dx > d[x] )
			continue;
		for ( const auto & y : G[x] ) 
			if ( d[y.first] > d[x] + y.second) {
				d[y.first] = d[x] + y.second;
				Q.push({d[y.first],y.first});
				}
		}
	for ( int i = 2; i <= n; ++i)
		if ( d[i] == 0x3f3f3f3f)
			fout << 0 << " ";
		else
		fout << d[i] << " ";
		
}