#include <vector>
#include <set>
#include <map>
#include <string.h>
#include <iostream>
using namespace std;

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

unsigned int costs[50005], source, dest, cost, current, nrE;
vector<vector<Edge*>> graph(50001);
map<unsigned int,set<int>> unvisited;
int i, n, m;

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

	memset(costs, -1 , 50005*4);

	costs[1] = 0;
	scanf("%d%d", &n, &m);

	for (i = 0; i < m; ++i)
	{
		scanf("%d%d%d", &source, &dest, &cost);
		graph.at(source).push_back(new Edge(dest, cost));
	}
	
	for (i = 2; i <= n; ++i) unvisited[-1].insert(i);
	unvisited[0].insert(1);

	while (!unvisited.empty())
	{
		current = *unvisited.begin()->second.begin();
		if (unvisited.begin()->second.size() == 1)	unvisited.erase(unvisited.begin());
		else unvisited.begin()->second.erase(current);
		nrE = graph.at(current).size();
		for (i = 0; i < nrE; ++i)
		{
			Edge *edge = graph.at(current).at(i);
			int dest = edge->destination;
			if (costs[dest]>costs[current] + edge->cost)
			{
				unvisited[costs[dest]].erase(dest);
				if (unvisited[costs[dest]].size() == 0)	unvisited.erase(costs[dest]);
				unvisited[costs[current] + edge->cost].insert(dest);
				costs[dest] = costs[current] + edge->cost;
			}
		}
	}

	for (i = 2; i <= n; ++i) printf("%d ", costs[i]!=-1 ? costs[i]:0);
	printf("\n");
}