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

using namespace std;

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

const int oo = (1 << 30);
const int NMax = 50005;

vector<pair<int, int>>v[NMax];

int n, m, d[NMax];
bool incoada[NMax];

struct compar {
	bool operator()(int x, int y) {
		return d[x] > d[y];
	}
};

priority_queue<int, vector<int>, compar>coada;

void dijkstra(int nodstart) {
	for (int i = 1; i <= n; i++) {
		d[i] = oo;
	}
	d[nodstart] = 0;
	coada.push(nodstart);
	incoada[nodstart] = true;
	while (!coada.empty()) {
		int nodcurent = coada.top();
		coada.pop();
		incoada[nodcurent] = false;
		for (size_t i = 0; i < v[nodcurent].size(); i++) {
			int vecin = v[nodcurent][i].first;
			int cost = v[nodcurent][i].second;
			if (d[nodcurent] + cost < d[vecin]) {
				d[vecin] = d[nodcurent] + cost;
				if (incoada[vecin] == false) {
					coada.push(vecin);
					incoada[vecin] = true;
				}
			}
		}
	}
}
int main() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		f >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++) {
		if (d[i] != oo)
			g << d[i] << ' ';
		else
			g << "0 ";
	}
	return 0;
}