#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[1000000], nodes[1000000], index[1000000], dim_heap;
void swap(int i, int j)
{
	int aux;
	index[nodes[i]] = j;
	index[nodes[j]] = i;
	aux = heap[i];
	heap[i] = heap[j];
	heap[j] = aux;
	aux = nodes[i];
	nodes[i] = nodes[j];
	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 != INT_MAX)
		{
			swap(pos, ind);
			pos = ind;
		}
		else
		{
			break;
		}
	}
}
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;

	fscanf(f, "%d %d", &n, &m);
	for (i = 1; i <= n; 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);
		insert_graph(L[v], u, r);
	}
	int sursa = 1;
	d[sursa] = 0;
	insert(1, 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 = 2; i <= n; i++)
	{
		fprintf(g, "%d ", d[i]);
	}

}