///Roy Floyd algorithm

/*
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("royfloyd.in");
ofstream g("royfloyd.out");

int inf = 10000000;
int n;
int dist[1005][1005];

int main() {
	f >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			f >> dist[i][j];
			if (dist[i][j] == 0) dist[i][j] = inf;
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i != j)
					dist[i][j] = min(dist[i][j], dist[k][j] + dist[i][k]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == inf)
				g << 0 << ' ';
			else
				g << dist[i][j] << ' ';
		}
		g << '\n';
	}
	return 0;
}
*/

///DJIKSTRA algorithm

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

set < pair < int, int > > s;
vector < pair <int, int > > v[50005];
int n, m, x ,y ,c;
bool viz[50005];
int dist[50005];
int inf = 1000000000;

int main() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		f >> x >> y >> c;
		v[x].push_back({ y, c });
	}
	dist[1] = 0;
	for (int i = 2; i <= n; i++) dist[i] = inf;
	s.insert({ 0, 1 });
	while (!s.empty()) {
		int nod = s.begin()->second;
		s.erase(s.begin());
		for (auto ed : v[nod]) {
			if (dist[ed.first] > dist[nod] + ed.second) {
				s.erase({ dist[ed.first], ed.first });
				dist[ed.first] = dist[nod] + ed.second;
				s.insert({ dist[ed.first], ed.first });
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (dist[i] == inf) g << 0 << " ";
		else g << dist[i] << " ";
	}
}