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

#define MAXN 50002
#define INF 0x3f3f3f3f

using namespace std;

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

int n, m, D[MAXN];
vector < pair <int, int> > G[MAXN]; 

void citire () {
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		fin >> x >> y >> w;
		G[x].push_back(make_pair(w, y)); 
	}
}

void initDist () {
	for (int i = 1; i <= n; ++i) {
		D[i] = INF;
	}
}

void Dijkstra (int nod) {
	D[nod] = 0;
	set < pair <int, int> > S;
	S.insert(make_pair(0, nod));
	while (!S.empty()) {
		int x = S.begin()->second;
		S.erase(S.begin());

		int size = G[x].size();
		for (int i = 0; i < size; ++i) {
			int y = G[x][i].second;
			int w = G[x][i].first;
			if (D[y] > D[x] + w) {
				if (D[y] != INF)
					S.erase(S.find(make_pair(D[y], y)));
				D[y] = D[x] + w;
				S.insert(make_pair(D[y], y));
			}
		}
	}

	for (int i = 2; i <= n; ++i) {
		if (D[i] != INF)
			fout << D[i] << " ";	
		else
			fout << 0 << " ";
	}

}

int main () {
	citire();
	initDist();
	Dijkstra(1);
}