// Bellman–Ford.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

struct edge {
	int a, b, cost;
};


int main()
{


	int n, m;
	int v = 0;

	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);

	cin >> n >> m;

	vector<edge> edges(m);

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[i].a = a-1;
		edges[i].b = b-1;
		edges[i].cost = c;
	}


	vector<int> d(n, INT32_MAX);


	d[v] = 0;
	while (true) {
		bool any = false;
		for (int i = 0; i < m; i++) {
			if (d[edges[i].a] < INT32_MAX) {
				if (d[edges[i].b] > d[edges[i].a] + edges[i].cost) {
					d[edges[i].b] = d[edges[i].a] + edges[i].cost;
					any = true;
				}
			}
		}
		if (!any) {
			break;
		}
	}

	for (int i = 0; i < n; i++) {
		if (d[i] == INT32_MAX) {
			d[i] = 30000;
		}
		cout << d[i] << " ";
	}

    return 0;
}