#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 51000
#define INF 100000

int N, M;
int dist[NMAX];
bool selected[NMAX];

using Graph = std::vector<std::vector<std::pair<int, int> > >;
Graph graph;

struct PairCmp {
	bool operator()(const std::pair<int,int>& p1, const std::pair<int,int>& p2) const {
		return p1.second > p2.second;
	}
};

using PQueue = std::priority_queue<std::pair<int,int>, 
								   std::vector<std::pair<int,int> >,
								   PairCmp>;
PQueue Q;

void relax(int vec, int nod, int w) {
	if (!selected[vec] && dist[vec] > dist[nod] + w) {
		dist[vec] = dist[nod] + w;
		Q.push(std::make_pair(vec, dist[vec]));
	}
}

void dijkstra(int start) {
	for (int i = 1; i <= N; ++i) {
		dist[i] = INF;
	}
	dist[start] = 0;
	Q.push(std::make_pair(start, 0));

	while (!Q.empty()) {
		int nod = Q.top().first;
		Q.pop();

		if (selected[nod])
			continue;

		selected[nod] = true;

		for (std::pair<int,int> neigh : graph[nod]) {
			relax(neigh.first, nod, neigh.second);
		}
	}

}

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

	f >> N >> M;
	graph.resize(N+1);

	for (int i = 0; i < M; ++i) {
		int u, v, cost;
		f >> u >> v >> cost;
		graph[u].push_back(std::make_pair(v, cost));
	}

	int start = 1;

	dijkstra(start);
	for (int i = 2; i <= N; ++i) {
		if (dist[i] == INF) 
			g << 0 << " ";
		else
			g << dist[i] << " ";
	}

	f.close(); g.close();

	return 0;
}