#include <vector>
#include <string.h>
#include <stdio.h>
using namespace std;

struct Edge
{
	int destination;
	int cost;
	Edge(int dest, int c)
	{
		destination = dest;
		cost = c;
	}
};

unsigned int costs[50005], heapCosts[50005], source, dest, cost;
vector<vector<Edge*>> graph;
int i, n, m, nodes[50005], current, nmbUnvisited, sizel;

void pushDown(int pos)
{
	int aux = pos;

	if ((pos * 2 + 1 < nmbUnvisited && pos * 2 + 1 != -1) && heapCosts[aux] > heapCosts[pos * 2 + 1])	aux = pos * 2 + 1;
	if ((pos * 2 + 2 < nmbUnvisited && pos * 2 + 2 != -1) && heapCosts[aux] > heapCosts[pos * 2 + 2])	aux = pos * 2 + 2;
	if (aux != pos)
	{
		int nmb = nodes[aux];
		nodes[aux] = nodes[pos];
		nodes[pos] = nmb;

		nmb = heapCosts[aux];
		heapCosts[aux] = heapCosts[pos];
		heapCosts[pos] = nmb;
		pos = aux;
		pushDown(aux);
	}
}

void pushUp(int pos)
{
	int aux = pos;

	if ((pos - 1) / 2 >= 0 && heapCosts[aux] < heapCosts[(pos - 1) / 2])	aux = (pos - 1) / 2;
	if (aux != pos)
	{
		int nmb = nodes[aux];
		nodes[aux] = nodes[pos];
		nodes[pos] = nmb;

		nmb = heapCosts[aux];
		heapCosts[aux] = heapCosts[pos];
		heapCosts[pos] = nmb;
		pos = aux;
		pushUp(aux);
	}
}

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

	scanf("%d%d", &n, &m);

	nmbUnvisited = n;
	for (i = 0; i < 50005; ++i) costs[i] = 4000000000;
	for (i = 0; i < 50005; ++i) heapCosts[i] = 4000000000;
	memset(nodes, -1, 50005 * 4);
	costs[1] = 0;
	heapCosts[0] = 0;
	for (i = 0; i < n; i++) nodes[i] = i + 1;

	graph = vector<vector<Edge*>>(n + 1);
	for (i = 0; i < m; ++i)
	{
		scanf("%d%d%d", &source, &dest, &cost);
		graph.at(source).push_back(new Edge(dest, cost));
	}

	while (nmbUnvisited>0)
	{
		current = nodes[0];
		nodes[0] = nodes[nmbUnvisited - 1];
		nodes[nmbUnvisited - 1] = -1;
		heapCosts[0] = heapCosts[nmbUnvisited - 1];
		heapCosts[nmbUnvisited--] = 4000000000;
		pushDown(0);
		sizel = graph[current].size();
		for (i = 0; i < sizel; ++i)
		{
			Edge * edge = graph.at(current).at(i);
			if (costs[edge->destination]>costs[current] + edge->cost)
			{
				costs[edge->destination] = costs[current] + edge->cost;
				heapCosts[nodes[edge->destination]] = costs[current] + edge->cost;
					pushUp(nodes[edge->destination]);
			}
		}
	}

	for (i = 2; i <= n; ++i)	printf("%d ", costs[i]);
}