#include <vector>
#include <unordered_set>
#include <string.h>
#include <stdio.h>
#include <iostream>
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(50001);
unordered_set<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);
	unvisited.insert(1);
	for (i = 0; i < m; ++i)
	{
		scanf("%d%d%d", &source, &dest, &cost);
		graph.at(source).push_back(new Edge(dest, cost));
		unvisited.insert(source);
	}


	auto it = unvisited.begin();
	while (it!=unvisited.end())
	{
		current = *it;
		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;
		}
		it++;
	}

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