// http://infoarena.ro/problema/bellmanford

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

#define INF INT_MAX

typedef struct node {
	int b, cost;
	struct node *next;
} Node;

Node **Next;
int n, m;

int *Cost;

int bellmanFord(int here) {
	int i;
	for (i = 0; i < n; ++ i)
		Cost[i] = INF;
	Cost[here] = 0;

	Node *begin, *end = (Node*)calloc(1, sizeof(Node)),
	     *curr, *helper;
	end->b = here;

	for (begin = end; begin != NULL; begin = begin->next) {
		here = begin->b;

		for (curr = Next[here]; curr != NULL; curr = curr->next) {
			if (Cost[here] == INF)
				continue;
			if (Cost[curr->b] > Cost[here] + curr->cost) {
				Cost[curr->b] = Cost[here] + curr->cost;

				helper = (Node*)calloc(1, sizeof(Node));
				helper->b = curr->b;
				helper->next = NULL;
				end->next = helper;
				end = helper;
			}
		}

		helper = begin->next;
		free(begin);
	}

	for (i = 0; i < n; ++ i)
		for (curr = Next[i]; curr != NULL; curr = curr->next)
			if (Cost[curr->b] > Cost[i] + curr->cost)
				return 1;
	return 0;
}

void addNext(int a, int b, int cost) {
	Node *helper = (Node*)calloc(1, sizeof(Node));
	helper->b = b;
	helper->cost = cost;
	helper->next = Next[a];

	Next[a] = helper;
}

void eraseNext() {
	int i;
	Node *curr, *helper;
	for (i = 0; i < n; ++ i) 
		for (curr = Next[i]; curr != NULL; curr = helper) {
			helper = curr->next;
			free(curr);
		}	
	free(Next);
}

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

	scanf("%d%d", &n, &m);
	Next = (Node**)calloc(n, sizeof(Node*));

	int i, a, b, c;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d%d", &a, &b, &c);
		addNext(a - 1, b - 1, c);
	}

	Cost = (int*)calloc(n, sizeof(int));
	bellmanFord(0);
	for (i = 1; i < n; ++ i)
		printf("%d ", Cost[i]);
	printf("\n");

	eraseNext();
	free(Cost);
	return 0;
}