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

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

using std::vector;
using std::string;
using std::pair;

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

	void read() {
		std::ifstream in{ input_file };
		in >> n >> m;

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

		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() {
		std::set<pair<int, int>> heap;
		distance[source] = 0;
		heap.insert(std::make_pair(0, source));

		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:
	Dijkstra(const string& input, const string& output) : n{ 0 }, m{ 0 }, source{ 1 }, input_file{ input }, output_file{ output }, distance(){};

	~Dijkstra() {
		delete[] graf;
	}

	void print() {
		std::ofstream out(output_file);
		read();
		solve();

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

		out.close();
	}
};

int main() {
	Dijkstra d = Dijkstra("dijkstra.in", "dijkstra.out");
	d.print();
}