#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Graph {
public:
	Graph(int _n) : n(_n), nodes(_n, std::list<std::pair<int, int>>()) { }

	void add(int u, int v, int c) {
		u = u - 1;
		v = v - 1;

		nodes[u].push_back({ v, c });
	}

	void print_shortest(int s) {
		s = s - 1;
		std::cout << "computing from " << s << std::endl;

		std::vector<int> cost(n, INT_MAX);
		std::set<std::pair<int, int>> t;

		cost[s] = 0;
		t.insert({ 0, s });

		while (!t.empty()) {
			std::set<std::pair<int, int>>::iterator least = t.begin();
			int k = least->second;
			t.erase(least);
			std::cout << "processing " << k << std::endl;

			for (std::pair<int, int> p : nodes[k]) {
				if (cost[p.first] > cost[k] + p.second) {
					std::set<std::pair<int, int>>::iterator it = t.find({ cost[p.first], p.first });
					if (it != t.end())
						t.erase(it);
					cost[p.first] = cost[k] + p.second;
					t.insert({ cost[p.first], p.first });
				}
			}
		}

		std::ofstream out("dijkstra.out");
		for (int i = 0; i < n; i++)
			if (i != s) {
				if (cost[i] != INT_MAX)
					out << cost[i] << " ";
				else
					out << "0 ";
			}
		out << "\n";
	}

private:
	int n;
	std::vector<std::list<std::pair<int, int>>> nodes;
};

int main() {
	int t;
	std::fstream in("dijkstra.in");

	int n;
	int m;
	in >> n >> m;
	Graph g(n);
	for (int a1 = 0; a1 < m; a1++) {
		int x;
		int y;
		int r;
		in >> x >> y >> r;
		g.add(x, y, r);
	}
	int s = 1;
	g.print_shortest(s);

	return 0;
}