#include<stdio.h>
#include<stdlib.h>
#define INT_MAX 250000001
typedef struct list
{
	int val;
	int cost;
	list *next;
};
list *L[50001] = { 0 };
void insert(list * & first, int val, int cost)
{
	list *elem;
	elem = (list *)malloc(sizeof(list));
	elem->val = val;
	elem->cost = cost;
	if (first == NULL)
	{
		elem->next = NULL;
		first = elem;
	}
	else
	{
		elem->next = first;
		first = elem;
	}
}
int main()
{
	FILE *f, *g;
	f = fopen("dijkstra.in", "r");
	g = fopen("dijkstra.out", "w");
	int N, E, d[50001], i, a, b, c, min, k, j, fare, cost;
	bool viz[50001] = { 0 };
	list *first;
	fscanf(f, "%d %d", &N, &E);
	for (i = 0; i < E; i++)
	{
		fscanf(f, "%d %d %d", &a, &b, &c);
		insert(L[a], b, c);
	}
	for (i = 1; i <= N; i++)
	{
		d[i] = INT_MAX;
	}
	min = 0;
	d[1] = 0;
	while (min != INT_MAX)
	{
		min = INT_MAX;
		for (i = 1; i <= N; i++)
		{
			if (viz[i] == false)
			{
				if (d[i] < min)
				{
					min = i;
					k = i;
				}
			}
		}
		if (min != INT_MAX)
		{
			viz[k] = true;
			first = L[k];
			while (first != NULL)
			{
				if (viz[first->val] == false && d[first->val] > d[k] + first->cost)
				{
					d[first->val] = d[k] + first->cost;
				}
				first = first->next;
			}
		}

	}
	for (i = 2; i <= N; i++)
	{
		if (d[i] == INT_MAX)
		{
			d[i] = 0;
		}
		fprintf(g, "%d ", d[i]);
	}
}