#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <climits>
#include <cassert>
#include <functional>

using namespace std;
using T = long int;
using ncost = pair<T, T>;
using graph = vector<vector<ncost>>;

vector<T> dijkstra(graph g, T s)
{
	size_t N = g.size();
	vector<T> dist(N);
	priority_queue<ncost, vector<ncost>, greater<ncost>> Q;

	dist[0] = 0;
	Q.push(make_pair(0, dist[0]));
	for (size_t i = 1; i < N; i++)
	{
		dist[i] = INT_MAX;
		Q.push(make_pair(dist[i], i));
	}

	while (!Q.empty())
	{
		pair<T, T> p = Q.top();
		T u = p.second, cu = p.first;
		Q.pop();

		if (cu > dist[u])
			continue;

		for (pair<T,T> p : g[u])
		{
			T v = p.second, lv = p.first;
			T alt = dist[u] + lv;
			if (alt < dist[v])
			{
				dist[v] = alt;
				Q.push(make_pair(alt, v));
			}
		}
	}

	return dist;
}

int main(int argc, char const *argv[])
{
	ifstream fin("dijkstra.in");
	assert(fin.is_open());
	ofstream fout("dijkstra.out");

	T N, M;
	fin >> N >> M;

	graph g(N);
	for (T i = 0; i < M; i++) {
		T s, d, c;
		fin >> s >> d >> c;

		g[s-1].push_back(make_pair(c, d-1));
	}

	vector<T> dist = dijkstra(g, 0);
	for (size_t i = 1; i < dist.size(); i++)
	{
		if (dist[i] != INT_MAX)
			fout << dist[i] << ' ';
		else
			fout << 0 << ' ';
	}

	return 0;
}