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

using namespace std;

const int MAXN = 50010;
const int MAXDIST = 2000100100;
vector < pair<int,int> > v[MAXN];
set <pair <int,int> > s;
int d[MAXN];

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

	int m, n;
	f >> n >> m;
	int x, y, c;
	for (int i = 1; i <= m; i++) {
		f >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
	}
	
	d[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = MAXDIST;
	}

	s.insert(make_pair(0,1));

	while (!s.empty()) {
		pair <int,int> minDistVertex = *s.begin();
		s.erase(s.begin());
		int vertex = minDistVertex.second;
		int dist = minDistVertex.first;

		for (size_t i = 0; i < v[vertex].size(); i++) {
			int y = v[vertex][i].first;
			int cost = v[vertex][i].second;
			if (d[y] > dist + cost) {
				if (s.find(make_pair(d[y],y)) != s.end()) {
					s.erase(make_pair(d[y],y));
				}
				d[y] = dist + cost;
				s.insert(make_pair(d[y], y));
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		if (d[i] == MAXDIST) {
			g << 0 << " ";
		} else {
			g << d[i] << " ";
		}
	}
	g << '\n';

	return 0;
}