#include <iostream>
#include <fstream>
#include<vector>
#include<utility>
#include<climits>
#include<queue>
using namespace std;

ifstream f("dijkstra.in");
vector< pair<int, int>> graf[50005];
vector<int> dist;
priority_queue < pair<int, int>> pq;

int main()
{
	int N, M;
	f >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y, c;
		f >> x >> y >> c;
		graf[x].push_back(make_pair(-c, y));
	}
	dist.resize(N + 1, INT_MAX);
	dist[1] = 0;
	pq.push(make_pair(0, 1));
	while (pq.empty() == false) {
		pair<int, int> best;
		best = pq.top();
		pq.pop();
		int nod = best.second;

		for (int i = 0; i < graf[nod].size(); i++) {
			int vecin = graf[nod][i].second;
			int cost = -graf[nod][i].first;
			if (dist[vecin] > dist[nod] + cost) {
				dist[vecin] = dist[nod] + cost;
				pq.push(make_pair(-dist[vecin], vecin));
			}
		}

	}

	for (int i = 1; i <= N; i++)
		if (dist[i] == INT_MAX)
			cout << 0 << ' ';
		else
			cout << dist[i] << ' ';

	f.close();
	return 0;
}