#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int kMaxN = 50005;
const int kInf = 0x3f3f3f3f;

int N, M;
vector<pair<int, int>> G[kMaxN];

struct HeapNode {
	int node, cost;
	HeapNode(int n, int c) : node(n), cost(c) {}
	bool operator<(const HeapNode &other) const {
		return cost > other.cost;
	}
};
priority_queue<HeapNode> q;

void Read() {
	ifstream fin("dijkstra.in");
	fin >> N >> M;
	while (M--) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].emplace_back(y, c);
	}
}

void Solve() {
	memset(dist, kInf, sizeof dist);
	dist[1] = 0;
	q.emplace(1, 0);
	while (!q.empty()) {
		int node = q.front().node;
		int cost = q.front().cost;
		q.pop();
		if (cost != dist[node])
			continue;
		for (auto it : G[node]) {
			int new_dist = cost + it.second;
			if (new_dist < dist[it.first]) {
				dist[it.first] = new_dist;
				q.emplace(it.first, new_dist);
			}
		}
	}
}

void Print() {
	ofstream fout("dijkstra.out");
	for (int i = 2; i <= N; ++i)
		fout << (dist[i] == kInf ? 0 : dist[i]) << " ";
	fout << "\n";
}

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