#define  _CRT_SECURE_NO_WARNINGS

#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 });
		// nodes[v].push_back({ u, c });
	}

	void print_shortest(int s, FILE *out) {
		s = s - 1;

		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);

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

		for (int i = 0; i < n; i++)
			if (i != s) {
				if (cost[i] != INT_MAX)
					fprintf(out, "%d ", cost[i]);
				else
					fprintf(out, "0 ");
			}
		fprintf(out, "\n");
	}

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

int main() {
	FILE *in = fopen("dijkstra.in", "r");

	int n;
	int m;
	fscanf(in, "%d %d", &n, &m);

	Graph g(n);
	for (int a1 = 0; a1 < m; a1++) {
		int x;
		int y;
		int r;
		fscanf(in, "%d %d %d", &x, &y, &r);

		g.add(x, y, r);
	}
	int s = 1;

	FILE *out = fopen("dijkstra.out", "w");
	g.print_shortest(s, out);
	fclose(out);

	return 0;
}