#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

void print_shortest(std::vector<std::list<std::pair<int, int>>>& nodes) {
	int n = nodes.size();
	std::vector<int> cost(n, INT_MAX);
	std::set<std::pair<int, int>> t;

	cost[0] = 0;
	t.insert({ 0, 0 });

	while (!t.empty()) {
		std::set<std::pair<int, int>>::iterator least = t.begin();
		int k = least->second;
		t.erase(least);
	
		for (std::pair<int, int> p : nodes[k]) {
			if (cost[p.first] > cost[k] + p.second) {
				std::set<std::pair<int, int>>::iterator it = t.find({ cost[p.first], p.first });
				if (it != t.end())
					t.erase(it);
				cost[p.first] = cost[k] + p.second;
				t.insert({ cost[p.first], p.first });
			}
		}
	}

	std::ofstream out("dijkstra.out");
	for (int i = 1; i < n; i++)
		if (cost[i] != INT_MAX)
			out << cost[i] << " ";
		else
			out << "0 ";
	out << "\n";
}


int main() {
	std::fstream in("dijkstra.in");

	int n;
	int m;
	in >> n >> m;

	std::vector<std::list<std::pair<int, int>>> nodes(n);

	for (int a1 = 0; a1 < m; a1++) {
		int x;
		int y;
		int r;
		in >> x >> y >> r;

		nodes[x - 1].push_back({y - 1, r});
	}
	print_shortest(nodes);

	return 0;
}