#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

class graph {
	vector<vector<pair<ulong, int>>> adj;
	ulong nodes;

public:
	graph(ulong nodes) : adj(nodes), nodes(nodes) {}

	void add_edge(ulong x, ulong y, int c) {
		adj[x].push_back({y, c});
	}

	vector<ulong> dijkstra(ulong src) {
		vector<ulong> dist(nodes, INF);
		vector<bool> visited(nodes, false);

		priority_queue<pair<ulong, ulong>> pq;
		pq.push({0, src});
		dist[src] = 0;
		
		while (!pq.empty()) {
			auto [current_dist, current] = pq.top();
			pq.pop();

			visited[current] = true;

			for (const auto& [neigh, cost] : adj[current])
				if (dist[current] + cost < dist[neigh]) {
					dist[neigh] = dist[current] + cost;
					pq.push({-dist[current] - cost, neigh});
				}
		}

		return dist;
	}
};

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

	exit(sizeof(size_t));
	
	ulong n, m;
	fin >> n >> m;

	graph g(n);
	for (ulong i = 0, x, y, c; i < m; ++i) {
		fin >> x >> y >> c;
		g.add_edge(x - 1, y - 1, c);
	}

	vector<ulong> ans = g.dijkstra(0);

	for (ulong i = 1; i < n; ++i)
		fout << (ans[i] == INF ? 0 : ans[i]) << ' ';
}