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

using namespace std;

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

const int oo = INT_MAX;
const size_t dim = 50001;
int n, m; //noduri, muchii
int d[dim]; //distantele
bool viz[dim];
struct cmp {
	bool operator()(int i, int j) {
		return d[i] > d[j];
	}
};

vector<pair<int, int >>G[dim]; //graful
priority_queue<int, vector<int>, cmp>pq;

void citire() {
	in >> n >> m;
	for (int i = 0; i < m; i++) {
		int nP, nF, cost;
		in >> nP >> nF >> cost;
		G[nP].push_back(make_pair(nF, cost));
	}
}

void dij(int nod) {
	for (int i = 1; i <= n; i++) {
		d[i] = oo;
	}
	d[nod] = 0;
	pq.push(nod);
	viz[nod] = true;
	while (pq.empty() == false) {
		int x = pq.top();
		pq.pop();
		//viz[x] = false;
		for (auto& nd : G[x]) {
			int vecin = nd.first;
			int cost = nd.second;
			if (d[vecin] > d[x] + cost) {
				d[vecin] = d[x] + cost;
				if (!viz[vecin]) {
					pq.push(vecin);
					viz[vecin] = true;
				}
			}
		}
	}
}


int main() {

	citire();
	dij(1);
	for (int i = 2; i <= n; i++) {
		if (d[i] == oo) {
			out << "0 ";
		}
		else 
			out << d[i] << " ";
	}

	return 0;
}