#include <fstream>
#include <iostream>
#include <queue>
#include <limits.h>
#include <utility>
#include <string.h>

#define NMAX 50004
#define INF (LLONG_MAX - 1)

typedef std::pair<int, int> Link;
typedef std::pair<Link, int> Edge;
typedef std::vector<Edge> EdgeContainer;
long long d[NMAX];
bool visited[NMAX];

class myComparison {
public:
	bool operator() (const int& n1, const int& n2) const {
		return d[n1] > d[n2];
	}
};

EdgeContainer neighbors[NMAX];

int main () {
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");

	int n, m, x, y, cost, i, next, ngh;
	fin >> n >> m;
	std::priority_queue<int, std::vector<int>, myComparison> nodesHeap;

	for (i = 1; i <= m; i++) {
		fin >> x >> y >> cost;
		neighbors[x].push_back(Edge(Link(x, y), cost));
	}

	for (i = 2; i <= n; i++) {
		d[i] = INF;
	}
	d[1] = 0;
	nodesHeap.push(1);

	while (!nodesHeap.empty()) {
		next = nodesHeap.top();
		nodesHeap.pop();
		// std::cout << "updating "<< next << ": ";
		visited[next] = true;
		for (EdgeContainer::iterator it = neighbors[next].begin();
			it != neighbors[next].end(); it++) {
			ngh = (it->first).second;
			if (!visited[ngh] && d[ngh] > d[next] + it->second) {
				// std::cout << '('<< ngh << ", "<< d[ngh] << ", ";
				d[ngh] = d[next] + it->second;
				// std::cout << d[ngh] <<"), ";
				nodesHeap.push(ngh);
			}
		}
			// std::cout << "\n";
	}

	for (i = 2; i <= n; i++) {
		if (d[i] == INF) {
			fout << "0 ";
		} else {
			fout << d[i] << ' ';
		}
	}
	fout << "\n";

	return 0;
}