#include <iostream>
#include <fstream>
#include <vector>
#define INF 1<<30

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

class PriorityQueue {
private:
	struct element {
		int first, second;
	};
	element *h;
	int size;
	void swap(element &x, element &y) {
		element temp = x;
		x = y;
		y = temp;
	}
public:
	PriorityQueue(int maxSize) {
		this->size = 0;
		h = new element[maxSize + 1];
	}

	element top() {
		return h[1];
	}

	bool empty() {
		return size == 0;
	}

	void push(element x) {
		h[++size] = x;

		int father = size / 2;
		int son = size;

		while (father) {

			if (h[father].first > h[son].first)
				this->swap(h[father], h[son]);
			else
				return;

			son = father;
			father /= 2;
		}
	}

	void pop() {
		h[1] = h[size];
		--size;

		int father = 1;
		int son = 2;

		while (son <= size) {

			int rightSon = son + 1;
			if (rightSon <= size && h[son].first > h[rightSon].first)
				son = rightSon;

			if (h[father].first > h[son].first)
				this->swap(h[father], h[son]);
			else
				return;

			father = son;
			son *= 2;
		}

	}


};

#define makeNode(a,b) std::make_pair(a, b)
typedef std::pair<int, int> Node;

class Graph {
private:
	int V; // No. of vertices
	std::vector<Node> *table;

public:
	Graph(int V) {
		this->V = V;
		table = new std::vector<Node>[V];
	}

	void addEdge(int x, int y, int cost) {
		table[x].push_back(makeNode(y, cost));
	}

	void dijkstra(int source) {
		PriorityQueue *h = new PriorityQueue(60000);

		std::vector<int> costs(V, INF);

		costs[source] = 0;
		h->push({ 0, source });

		while (!h->empty()) {
			int node = h->top().second;
			int cost = h->top().first;
			h->pop();

			if (costs[node] == cost) {
				std::vector<Node>::iterator it;
				for (it = table[node].begin(); it != table[node].end(); ++it) {

					int newCost = costs[node] + it->second;
					if (costs[it->first] > newCost) {
						costs[it->first] = newCost;
						h->push({ newCost, it->first });
					}

				}
			}
		}

		std::vector<int>::iterator it;
		for (it = costs.begin() + 2; it != costs.end(); ++it)
			if (*it == INF)
				g << 0 << " ";
			else
				g << *it << " ";
		g << '\n';
	}

};

int main() {
	int n;
	f >> n;

	Graph* myGraph = new Graph(n + 1);

	int m;
	f >> m;

	int x, y, cost;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y >> cost;
		myGraph->addEdge(x, y, cost);
	}

	myGraph->dijkstra(1);


	return 0;
}