#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <climits>

using namespace std;

ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");

void beolvas(vector<vector<pair<int, int>>> &graf, int m);
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start);
void dijkstra(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p);
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> >& ismeretlen);
//void dijkstra_ut(int v, vector<int>& d, vector<int>& p);

int main() {
	int n, m, start;
	be >> n >> m;
	start = 0;
	//be >> n >> m >> start;
	//start--;
	vector<vector<pair<int,int>>> graf(n);
	beolvas(graf, m);
	legrovidebb_ut(graf, n, start);
}

void beolvas(vector<vector<pair<int, int>>>& graf, int m) {
	for (int i = 0; i < m; i++) {
		int x, y, z;
		be >> x >> y >> z;
		graf[x-1].push_back(make_pair((y-1), z));
	}
}

void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start) {
	vector<int> d(n, -1);
	vector<int> p(n, -1);

	dijkstra(graf, n, start, d, p);

	for (int i = 1; i < n; i++) {
		if (d[i] == INT_MAX)
			ki << "0 ";
		else ki << d[i] << " ";
	}

	/*for (int i = 0; i < n; i++) {
		if (i != start) {
			if (d[i] != INT_MAX) {
				ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: " << d[i] << "\n";
				ki << "A legrovidebb ut " << i+1 << "-ba/be: ";
				dijkstra_ut(i, d, p);
			}
			else {
				ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: Nem lehet eljutni!" << "\n";
				ki << "A legrovidebb ut " << i+1 << "-ba/be: Nem lehet eljutni!" << "\n";
			}
		}
	}*/
}

void dijkstra(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> > ismeretlen;
	for (int i = 0; i < n; i++) {
		d[i] = INT_MAX;
	}

	d[start] = 0;
	ismeretlen.push({ 0,start });

	while (!ismeretlen.empty()) {
		auto best = ismeretlen.top();
		int du = best.first;
		int u = best.second;

		ismeretlen.pop();
		if (du != d[u]) continue;

		if (d[u] != INT_MAX)
			relax(graf, u, d, p, ismeretlen);

		/*for (auto p : graf[u]) {
			int v = p.first;
			int edge = p.second;

			if (d[v] > edge + du) {
				d[v] = edge + du;
				ismeretlen.push({ d[v],v });
			}
		}*/
	}
}

void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> >&ismeretlen) {
	for (auto i : graf[v]) {
		int w = i.first;
		if ((d[v] != INT_MAX) && (d[w] > (d[v] + i.second))) {
			d[w] = d[v] + i.second;
			p[w] = v;
			ismeretlen.push({ d[w],w });
		}
	}
}

/*void dijkstra_ut(int v, vector<int>& d, vector<int>& p) {
	int k = d[v];
	vector<int> ut;
	ut.push_back(v);
	while (k > 0 && p[ut[ut.size() - 1]]!=-1) {
		ut.push_back(p[ut[ut.size() - 1]]);
		k-=d[ut[ut.size() - 1]];
	}
	
	for (int i = ut.size() - 1; i >= 0; i--) {
		ki << ut[i]+1 << " ";
	}
	ki << "\n";
}*/