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

struct Edge
{
	int destination;
	int cost;
	Edge(int dest, int c)
	{
		destination = dest;
		cost = c;
	}
};
int i, n, m, costs[50005],source,dest,cost,current,nrE;
vector<vector<Edge*>> graph;
deque<int> unvisited;


int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	memset(costs, -1, 50005);
	costs[1] = 0;
	scanf("%d%d", &n, &m);
	graph.push_back(vector<Edge*>());
	for (i = 0; i < m; ++i)
	{
		scanf("%d%d%d", &source, &dest, &cost);
		while (graph.size() < source + 1 || graph.size() < dest + 1)	graph.push_back(vector<Edge*>());
		graph.at(source).push_back(new Edge(dest, cost));
	}

	for (i = 1; i <= n; ++i)	unvisited.push_back(i);

	while (unvisited.size()>0)
	{
		current = unvisited.at(0);
		unvisited.pop_front();
		nrE = graph.at(current).size();
		for (i = 0; i < nrE; ++i)
		{
			Edge *edge = graph.at(current).at(i);
			if (costs[edge->destination]>costs[current] + edge->cost || costs[edge->destination] == -1)	costs[edge->destination] = costs[current] + edge->cost;
		}
	}

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