#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>

const int COST_MAX = 999999;

struct Pair {
	int nod, cost;
	Pair(int nod = 0, int cost = 0) : nod(nod), cost(cost) {}
};

struct PairCompare {
	bool operator() (const Pair& lhs, const Pair& rhs) const {
		return lhs.cost < rhs.cost;
	}
};

std::vector<Pair> graf[50000];
int dist[50000];

void dijkstra(int start)
{
	std::priority_queue<Pair, std::vector<Pair>, PairCompare> pq;
	pq.push(Pair(start, 0));
	dist[start] = 0;

	while(!pq.empty())
	{
		Pair u = pq.top();
		pq.pop();

		if(u.cost != dist[u.nod])
			continue;

		for(size_t i = 0; i < graf[u.nod].size(); i++)
		{
			Pair v = graf[u.nod][i];
			if(dist[v.nod] > dist[u.nod] + v.cost)
			{
				dist[v.nod] = dist[u.nod] + v.cost;
				pq.push(Pair(v.nod, dist[v.nod]));
			}
		}
	}
}

int main()
{
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");
	if(!fin.is_open() || !fout.is_open())
		return -1;

	int n = 0, m = 0, a = 0, b = 0, c = 0;
	fin >> n >> m;

	std::fill_n(dist, n, COST_MAX);

	for(int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		graf[a - 1].push_back(Pair(b - 1, c));
	}

	dijkstra(0);

	for(int i = 1; i < n; i++)
		fout << (dist[i] == COST_MAX ? 0 : dist[i]) << ' ';

	fout << '\n';

	return 0;
}