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

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 node = heap.begin()->second;
			heap.erase(heap.begin());

			for (auto muchie : graf[node]) {
				if (distance[muchie.nod] > distance[node] + muchie.cost) {
					if (distance[muchie.nod] != oo) {
						heap.erase(heap.find(std::make_pair(distance[muchie.nod], muchie.nod)));
					}
					distance[muchie.nod] = distance[node] + muchie.cost;
					heap.insert(std::make_pair(distance[muchie.nod], muchie.nod));
				}
			}
		}
	}

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

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

		for (int i = 2; i <= n; ++i) {
			if (distance[i] != oo) {
				out << distance[i] << " ";
			}
			else {
				out << 0 << " ";
			}
		}

		out.close();
	}

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

int main() {

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

	return 0;
}