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

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

#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) {
		std::priority_queue< Node, std::vector<Node>, std::greater<Node> > h;

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

		costs[source] = 0;
		h.push(makeNode(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(makeNode(newCost, it->first));
					}

				}
			}
		}

		std::vector<int>::iterator it;
		for (it = costs.begin() + 2; it != costs.end(); ++it)
			if (*it == INF)
				g << -1 << " ";
			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;
}