#include <fstream>

#include <vector>

#include <set>

using namespace std;

ifstream fin ("dijkstra.in");

ofstream fout ("dijkstra.out");

int main () {

	int n, m;

	fin >> n >> m;

	vector<vector<pair<int, int>>> graph (n + 1);

	for (int i = 1; i <= m; ++i) {

		int a, b, c;

		fin >> a >> b >> c;

		graph[a].push_back({b, c});
	}

	long long MAX = 1LL << 60;

	vector<long long> cost (n + 1, MAX);

	cost[1] = 0;

	set<pair<long long, int>> s;

	s.insert({0, 1});

	while (!s.empty()) {

		pair <long long, int> minim = *s.begin();

		s.erase(minim);

		for (int i = 0; i < graph[minim.second].size(); ++i) {

			int vecin = graph[minim.second][i].first;

			int val = graph[minim.second][i].second;

			if (minim.first + val < cost[vecin]) {

				if (s.find({cost[vecin], vecin}) != s.end())
					s.erase({cost[vecin], vecin});
				
				cost[vecin] = minim.first + val;

				s.insert({cost[vecin], vecin});
			}
		}
	}

	for (int i = 2; i <= n; ++i) {
		
		if (cost[i] == MAX)
			fout << 0 << ' ';
		else
			fout << cost[i] << ' ';
	}
	
	return 0;
}