#include <fstream>
#include <vector>
#include <stdlib.h>

using namespace std;

#define INF 1000000000

long x, y, c, cost[50010], n, m, i, Q[1000000], j, dex[50010];
vector <long> v[50010][2];

int main() {
	ifstream f("bellmanford.in");
	ofstream h("bellmanford.out");
	
	f>>n>>m;

	for (i = 1; i <= n; ++i) cost[i] = INF;
	cost[1] = 0;
	
	for (i = 1; i <= m; ++i) {
		f>>x>>y>>c;
		v[x][0].push_back(y);
		v[x][1].push_back(c);
	}
	
	
	Q[++Q[0]] = 1;
	++dex[1];
	for (i = 1; i <= Q[0]; ++i) {
		long s = v[Q[i]][0].size();
		for (j = 0; j < s; ++j) {
			if (cost[Q[i]] + v[Q[i]][1][j] < cost[v[Q[i]][0][j]]) {
				cost[v[Q[i]][0][j]] = cost[Q[i]] + v[Q[i]][1][j];
				if (dex[v[Q[i]][0][j]] < n) Q[++Q[0]] = v[Q[i]][0][j], ++dex[v[Q[i]][0][j]];
			}
		}
	}
	
	
	/*long H = 0;
	long aux = 1;
	while (aux && H < n + 2) {
		aux = 0;
		++H;
		for (i = 1; i <= m; ++i) {
			if (cost[x[i]] + c[i] < cost[y[i]]) {
				cost[y[i]] = cost[x[i]] + c[i];
				aux = 1;
			}
			++k;
		}
	}*/
	
	/*if (Q[0] >= n + 2) {
		h<<"Ciclu negativ!\n";
	} else {*/
		for (i = 2; i <= n; ++i) {
			h<<cost[i]<<" ";
		}
	//}
		
	return 0;
}