#include <bits/stdc++.h>
#define Nmax 50050
#define INF (1 << 30)

using namespace std;

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

int N, dp[Nmax];
vector < pair < int, int > > L[Nmax];
priority_queue <pair <int, int> > q;
bool used[Nmax];

inline void Read() {
	int i, M, x, y, c;
	fin >> N >> M;
	for (i = 1; i <= M; i++) {
		fin >> x >> y >> c;
		L[x].push_back({ y, c });
	}
	fin.close();
}

inline void Solve() {
	int i, cost, node, newNode;
	for (i = 2; i <= N; i++)
		dp[i] = INF;
	dp[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		node = q.top().second;
		q.pop();
		if (!used[node]) {
			used[node] = 1;
			for (auto it : L[node]) {
				newNode = it.first;
				cost = it.second;
					dp[newNode] = dp[node] + cost;
					q.push({ -dp[newNode], newNode });
			}
		}
	}
}

inline void Write() {
	int i;
	for (i = 2; i <= N; i++)
		if (dp[i] == INF) fout << "0 ";
		else fout << dp[i] << " ";
	fout << "\n";
	fout.close();
}

int main() {
	Read();
	Solve();
	Write();
	return 0;
}