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

using namespace std;

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

const int INF = 0x7fffffff;
const int NMAX = 50000;

int n;
vector < pair <int, int> > graf[NMAX + 1];
int d[NMAX + 1];

void citeste() {
	int e, a, b, c;
	f >> n >> e;
	for (int i = 1; i <= e; i++) {
		f >> a >> b >> c;
		graf[a].push_back(make_pair(b, c));
	}
}

void rezolva(int sursa) {
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[sursa] = 0;

	set < pair <int, int> > s;
	s.insert(make_pair(0, sursa));

	while (!s.empty()) {
		pair <int, int> p = *(s.begin());
		s.erase(s.begin());

		int c = p.first;
		int nod = p.second;

		int l = graf[nod].size();
		for (int i = 0; i < l; i++) {
			int fiu = graf[nod][i].first;
			if (d[fiu] > c + graf[nod][i].second) {
				d[fiu] = c + graf[nod][i].second;
				s.insert(make_pair(d[fiu], fiu));
			}
		}
	}
}

void scrie() {
	for (int i = 2; i <= n; i++) {
		if (d[i] == INF) d[i] = 0;
		g << d[i] << ' ';
	}
	g << '\n';
}

int main() {
	citeste();
	rezolva(1);
	scrie();
	return 0;
}