// Dijkstra.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

const int maxn = 1e5 + 5;
const int oo = 1 << 30;
vector < pair <int, int> > G[maxn];
int Dist[maxn];

void Dijkstra(int n, int source) {
	priority_queue < pair <int, int> > Q;
	bitset <maxn> Vis = 0;
	for (int i = 1; i <= n; i++) {
		Dist[i] = oo;
	}
	Dist[source] = 0;
	Q.push(make_pair(0, source));
	while (!Q.empty()) {
		int node = Q.top().second;
		Q.pop();
		if (Vis[node] == true) continue;
		Vis[node] = true;
		for (auto &it : G[node]) {
			if (Dist[it.first] > Dist[node] + it.second) {
				Dist[it.first] = Dist[node] + it.second;
				Q.push(make_pair(-Dist[it.first], it.first));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, m, x, y, c;
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	Dijkstra(n, 1);
	for (int i = 2; i <= n; i++) {
		if (Dist[i] == oo) {
			fout << "0 ";
		} else {
			fout << Dist[i] << ' ';
		}
	}
	fout << "\n";
	fin.close();
	fout.close();
	return 0;
}