#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 50005, INF = 0x3f3f3f3f;

struct Node {
	int node, cost;
	Node(int n, int c) {
		node = n;
		cost = c;
	}
	bool operator<(const Node &other) const {
		return cost > other.cost;
	}
};
int N, M, dist[NMAX];
vector<pair<int, int>> G[NMAX];
priority_queue<Node> Q;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int main() {
	fin >> N >> M;
	while (M--) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	memset(dist, INF, sizeof dist);
	dist[1] = 0;
	Q.push(Node(1, 0));
	while (!Q.empty()) {
		int node = Q.top().node, cost = Q.top().cost;
		Q.pop();
		if (cost > dist[node])
			continue;
		for (auto it : G[node]) {
			int new_dist = cost + it.second;
			if (new_dist < dist[it.first]) {
				dist[it.first] = new_dist;
				Q.push(Node(it.first, new_dist));
			}
		}
	}
	for (int i = 2; i <= N; ++i)
		if (dist[i] == INF)
			fout << "0 ";
		else
			fout << dist[i] << " ";
	return 0;
}