#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <fstream>

using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
using std::set;
using std::pair;

#define arc pair<int, int>
#define nod first;
#define cost second
#define oo 0x3f3f3f3f


class Solve {
private:
	string input_file;
	string output_file;
	vector<arc>* graf;
	vector<int> distance;
	int n, m, source;

	void read() {
		ifstream in(input_file);

		in >> n >> m;
		distance.resize(n + 1, oo);
		graf = new vector<arc>[n + 1];

		int x, y, w;
		for (int i = 1; i <= m; ++i) {
			in >> x >> y >> w;
			graf[x].push_back(std::make_pair(y, w));
		}

		in.close();
	}

	void solve() {
		read();

		set<pair<int, int>> heap;
		heap.insert(std::make_pair(0, source));
		distance[source] = 0;

		while (!heap.empty()) {
			int first = heap.begin()->second;
			heap.erase(heap.begin());

			for (const auto& muchie : graf[first]) {
				if (distance[muchie.first] > distance[first] + muchie.second) {
					if (distance[muchie.first] != oo) {
						heap.erase(heap.find(std::make_pair(distance[muchie.first], muchie.first)));
					}
					distance[muchie.first] = distance[first] + muchie.second;
					heap.insert(std::make_pair(distance[muchie.first], muchie.first));
				}
			}
		}
	}

public:
	Solve(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};

	void print() {
		solve();
		ofstream out(output_file);

		for (int i = 2; i <= n; ++i) {
			out << distance[i] << " ";
		}

		out.close();
	}

	~Solve() {
		delete[] graf;
	}
};

int main() {

	Solve s = Solve("dijkstra.in", "dijktra.out");
	s.print();

	return 0;
}