#include <queue>
#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;
vector < int > D;
priority_queue < pair < int, int > , vector < pair < int , int > > , greater< pair < int, int > > > Q;

int n,m,cost;

int main() {
	
	fin >> n >> m;
	G = VVI ( n + 1);
	int x,y,cost;
	for ( ; m > 0; --m) {
		fin >> x >> y >> cost;
		G[x].push_back({y,cost});
	}
	D = vector < int > ( n + 1, 0x3f3f3f3f);
	D[1] = 0;
	Q.push({0,1});
	while ( !Q.empty() ) {
		int x = Q.top().second;
		int dx = Q.top().first;
		Q.pop();
		if ( dx > D[x])
			continue;
		for ( const auto & y : G[x] ) 
			if ( D[y.first] > dx + y.second) {
				D[y.first] = dx + 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] << " ";
}