#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define maxn 50001

#define INF 0x3f3f3f3f
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int main() {

	priority_queue <pair <int, int>, vector <pair <int, int> >,
					greater <pair <int, int> > > priorityQ;

	int N, M;
	in >> N >> M;

	vector <pair <int, int> > G[maxn];

	for (int i = 1; i <= M; i++) {
		int x, y, c;
		in >> x >> y >> c;
		G[x].push_back(make_pair(c, y));
	}

	vector <int> D;
	D.push_back(0);
	
	for (int i = 2; i <= N; i++) {
		D.push_back(INF);
	}

	priorityQ.push(make_pair(0, 1));

	while(!priorityQ.empty()) {

		pair <int, int> current = priorityQ.top();
		priorityQ.pop();
		if (D[current.second] == current.first) {

			for(pair<int, int> aux : G[current.second]) {

				if (D[current.second] + aux.first < D[aux.second]) {
					D[aux.second] = D[current.second] + aux.first;
					priorityQ.push(make_pair(D[aux.second], aux.second));
				}
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		if(D[i] != INF)
			out << D[i] << ' ';
		else
			out << 0 << ' ';
	}
	return 0;
}