#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define pi std::pair<int,int>
#define x first
#define y second

const int nmax = 5e4 + 5;

int d[nmax];
std::priority_queue<pi>q;
std::vector<pi>l[nmax];

void dijkstra() {
	q.push({ 0, 1 });
	while (!q.empty()) {
		auto a = q.top();
		q.pop();
		if (d[a.y] != -1) continue;
		d[a.y] = -a.x;
		for (auto b : l[a.y]) q.push({ a.x - b.y, b.x });
	}
}

int main() {
	std::ifstream f("dijkstra.in");
	std::ofstream g("dijkstra.out");
	int n, m, u, v, c;
	f >> n >> m;
	for (int i = 1; i <= n; i++) d[i] = -1;
	for(int i=1;i<=m;i++){
		f >> u >> v >> c;
		l[u].push_back({ v, c });
	}
	dijkstra();
	for (int i = 2; i <= n; i++) d[i] = ((d[i] == -1) ? 0 : d[i]), g << d[i] << " ";
}