#include <stdio.h>
#include <stdlib.h>
#define INT_MAX 1000000000
typedef struct list
{
	int val;
	int cost;
	list *next;
};
list *L[50001];
void insert_graph(list * &head, int val, int cost)
{
	list *elem;
	elem = (list *)malloc(sizeof(list));
	elem->val = val;
	elem->cost = cost;
	if (head == NULL)
	{
		elem->next = NULL;
		head = elem;
	}
	else
	{
		elem->next = head;
		head = elem;
	}
}
int heap[50001], nodes[50001], index[50001], dim_heap;
void swap(int i, int j)
{
	int aux;
	aux = heap[i];
	heap[i] = heap[j];
	heap[j] = aux;
	aux = nodes[i];
	nodes[i] = nodes[j];
	nodes[j] = aux;
	aux = index[nodes[i]];
	index[nodes[i]] = index[nodes[j]];
	index[nodes[j]] = aux;
}
int get_parent(int pos)
{
	if (pos % 2 == 0)
	{
		return (pos - 2) / 2;
	}
	return (pos - 1) / 2;
}
void UP(int pos)
{
	int parent;
	while (pos > 0)
	{
		parent = get_parent(pos);
		if (heap[parent] > heap[pos])
		{
			swap(parent, pos);
			pos = parent;
		}
		else
		{
			break;
		}
	}
}
void DOWN(int pos)
{
	int r, l, min, ind;
	/*while (true)
	{
		r = 2 * pos + 2;
		l = 2 * pos + 1;
		if (r >= dim_heap)
		{
			heap[r] = INT_MAX;
		}
		if (l >= dim_heap)
		{
			heap[l] = INT_MAX;
		}
		min = INT_MAX;
		if (heap[r] < min)
		{
			min = heap[r];
			ind = r;
		}
		if (heap[l] < min)
		{
			ind = l;
		}
		if (min < heap[pos])
		{
			swap(pos, ind);
			pos = ind;
		}
		if (min == INT_MAX || min >= heap[pos])
		{
			break;
		}
	}*/
	while (pos < dim_heap)
	{
		ind = 2 * pos + 1;
		if (ind + 1 < dim_heap && heap[ind + 1] < heap[ind])
		{
			ind++;
		}
		if (heap[pos]>heap[ind])
		{
			swap(pos, ind);
			pos = ind;
		}
		else
		{
			break;
		}
	}
	/*while (pos < (dim_heap >> 1)) {
		int child = 2 * pos + 1;
		if (child + 1 < dim_heap && heap[child + 1] < heap[child]) {
			++child;
		}
		if (heap[pos] <= heap[child]) {
			break;
		}
		swap(pos, child);
		pos = child;
	}*/
}
void insert(int cost, int nod)
{
	heap[dim_heap] = cost;
	nodes[dim_heap] = nod;
	index[nod] = dim_heap;
	UP(dim_heap);
	dim_heap++;
}
void update(int cost, int nod)
{
	int pos;
	pos = index[nod];
	heap[pos] = cost;
	UP(pos);
}
int del()
{
	int res = nodes[0];
	dim_heap--;
	heap[0] = heap[dim_heap];
	nodes[0] = nodes[dim_heap];
	index[nodes[0]] = 0;
	DOWN(0);
	return res;
}
int main()
{
	FILE *f, *g;
	f = fopen("dijkstra.in", "r");
	g = fopen("dijkstra.out", "w");
	int t, n, m, i, d[50001], u, v, r, fare;
	t = 1;
	while (t--)
	{
		list *p;
		fscanf(f, "%d %d", &n, &m);
		for (i = 0; i <= n + 1 ; i++)
		{
			d[i] = INT_MAX;
			L[i] = NULL;
		}
		for (i = 0; i < m; i++)
		{
			fscanf(f, "%d %d %d", &u, &v, &r);
			insert_graph(L[u], v, r);

		}
		int sursa = 1;
		d[sursa] = 0;
		insert(0, sursa);
		while (dim_heap)
		{
			int nod = del();
			list *p = L[nod];
			while (p != NULL)
			{
				fare = p->cost;
				if (d[p->val] > d[nod] + fare)
				{
					if (d[p->val] == INT_MAX)
					{
						insert(d[nod] + fare, p->val);
						d[p->val] = d[nod] + fare;
					}
					else
					{
						update(d[nod] + fare, p->val);
						d[p->val] = d[nod] + fare;
					}
				}
				p = p->next;
			}
		}

		for (i = 1; i <= n; i++)
		{
			if (i != sursa)
			{
				if (d[i] == INT_MAX)
				{
					d[i] = 0;
				}
				fprintf(g, "%d ", d[i]);
			}
		}
		fprintf(g, "\n");
	}

}