#include <bits/stdc++.h>

class Solution {
public:
	std::vector<int> getMinDistances(std::vector<std::vector<std::pair<int, int>>>& g) {
		int n = g.size() - 1;
		int visNodesNo = 0;
		std::vector<int> dist(n + 1, INT_MAX);
		std::priority_queue<std::pair<int, int>> pq;

		pq.push({0, 1});
		dist[1] = 0;

		while (!pq.empty()) {
			int nodeDist = pq.top().first;
			int node = pq.top().second;
			nodeDist = -nodeDist;

			pq.pop();

			visNodesNo++;
			if (visNodesNo == n) {
				return dist;
			}

			for (auto p : g[node]) {
				int neigh = p.first;
				int neighDist = p.second;

				int newDist = nodeDist + neighDist;
				if (dist[neigh] > newDist) {
					dist[neigh] = newDist;
					pq.push({-newDist, neigh});
				}
			}
		}

		return dist;
	}

	std::vector<std::vector<std::pair<int, int>>> readGraph(std::ifstream& fin) {
		int n, m;
		fin >> n >> m;

		std::vector<std::vector<std::pair<int, int>>> g(n + 1, std::vector<std::pair<int, int>>());

		for (int i = 0; i < m; ++i) {
			int node1, node2, dist;
			fin >> node1 >> node2 >> dist;

			g[node1].push_back({node2, dist});
		}

		return g;
	}

	void printDist(std::vector<int>& dist, std::ofstream& fout) {
		for (int i = 2; i <= dist.size(); ++i) {
			fout << (dist[i] == INT_MAX ? 0 : dist[i]) << " ";
		}

		fout << std::endl;
	}
};

int main() {
	Solution solution;

	std::ifstream fin("dijkstra.in");
	auto g = solution.readGraph(fin);
	fin.close();

	auto dist = solution.getMinDistances(g);

	std::ofstream fout("dijkstra.out");
	solution.printDist(dist, fout);
	fout.close();

	return 0;
}