#include <bits/stdc++.h>
#define dim 50005
#define oo 100000000

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

using namespace std;
int distante[dim]; int nrNoduri, nrMuchii;
bool vizitat[dim];
vector< pair<int, int> >graf[dim];

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

priority_queue<int, vector<int>, cmpD>q;

void citire() {
	in >> nrNoduri >> nrMuchii;
	for (int i = 1; i <= nrMuchii; ++i) {
		int x, y, c;
		in >> x >> y >> c;
		graf[x].push_back(make_pair(y, c));
		//graf[y].push_back(make_pair(x,c));
	}
}

void diji(int nod) {

	for (int i = 1; i <= nrNoduri; ++i) {
		if (i != nod) {
			distante[i] = oo;
		}
	}

	for (int i = 1; i <= nrNoduri; i++) {
		q.push(i);
	}

	while (!q.empty()) {
		int x = q.top();
		q.pop();
		vizitat[x] = true;
		for (size_t i = 0; i < graf[x].size(); i++) {
			int vecin = graf[x][i].first;
			int cost = graf[x][i].second;
			if (distante[vecin] > distante[x] + cost) {
				distante[vecin] = distante[x] + cost;
				if (!vizitat[vecin]) {
                    vizitat[vecin] = true;
                    q.push(vecin);
				}
			}
		}
	}
}
int main() {
	citire();
	diji(1);
	for (int i = 2; i <= nrNoduri; i++) {
		if (distante[i] == oo) {
			out << "0" << ' ';
		}
		else {
			out << distante[i] << ' ';
		}
	}

	return 0;
}