#include <bits/stdc++.h>
using namespace std;
#define int long long

#define N 1005
#define inf INT_MAX
int n, m, yd; //点，边，源点
int d[N];//从源点到当前点的最短路径
int p[N];//前驱

struct edge {
	int dd; //到达
	int len;//长度
};
vector<edge> a[N];

signed main() {
	memset(p, -1, sizeof(p));
	memset(d, inf, sizeof(d));
	cin >> n >> m;
	d[yd] = 0;
	for (int i = 1; i <= m; i++) {
//		cin >> a[i].cf >> a[i].dd >> a[i].len;
		int cf, dd, len;
		cin >> cf >> dd >> len;
		a[cf][i].dd = dd;
		a[cf][i].len = len;
	}
	for (int i = 1; i <= n; i++) {
		bool flag = 0;
		for (int j = 1; j <= m; j++) {
			for (auto x : a[j]) {
				int dd = x.dd, len = x.len;
				if (d[dd] > d[j] + len) {
					d[dd] = d[j] + len;
					p[dd] = j;
					flag = 1;
				}
			}
		}
		if (!flag) {
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << d[i] << " ";
	}
	cout << endl;
	return 0;
}