#include <fstream>
#include <vector>
#include <queue>

using namespace std;
#define Nmax 50005
#define Inf (1<<30)
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
vector<pair<int, int>>g[Nmax];
int n, m, cost[Nmax], viz[Nmax];

void dij() {
	int i, nc;
	for (i = 1; i <= n; i++) {
		cost[i] = Inf;
	}
	cost[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		nc = q.top().second;
		q.pop();
		if (viz[nc]) continue;
		viz[nc] = 1;
		for (auto nn:g[nc]) {
			if (cost[nc] + nn.first >= cost[nn.second]) continue;
			cost[nn.second] = cost[nc] + nn.first;
			q.push({ cost[nn.second], nn.second });
		}
	}
}

int main() {
	int i, x, y, z;
	fin >> n >> m;
	for (i = 0; i < m; i++) {
		fin >> x >> y >> z;
		g[x].push_back({z,y});
	}
	dij();
	for (i = 2; i <= n; i++) {
		if (cost[i] == Inf) fout << 0 << ' ';
		else fout << cost[i] << ' ';
	}
}