#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

typedef struct Edge
{
	int start;
	int end;
	int weight;
}Edge;

int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int n, m, x, y, c;
	scanf("%d%d", &n, &m);

	int* vertex = (int*)calloc(n, sizeof(int));
	assert(vertex); vertex[0] = 0;
	for (int i = 1; i < n; i++) vertex[i] = 10000;
	Edge* edges_list = (Edge*)calloc(m, sizeof(Edge));
	assert(edges_list);

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &x, &y, &c);
		edges_list[i].start = x - 1;
		edges_list[i].end = y - 1;
		edges_list[i].weight = c;
	}

	for (int t = 1; t < n; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (edges_list[j].start == i) {
					int st = i;
					int dr = edges_list[j].end;
					int cost = edges_list[j].weight;
					if (vertex[st] + cost < vertex[dr])
						vertex[dr] = vertex[st] + cost;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		printf("%d ", vertex[i]);
	}

	free(vertex);
	free(edges_list);

	return 0;
}