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

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


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

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

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

		if (cu > dist[u])
			continue;

		for (pair<int,int> p : g[u])
		{
			int v = p.second, lv = p.first;
			int 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");

	int N, M;
	fin >> N >> M;

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

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

	vector<int> dist = dijkstra(g, 0);
	for (int i = 1; i < dist.size(); i++)
	{
		fout << dist[i] << ' ';
	}

	return 0;
}