#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;
const int INF = 2e9;

struct Edge {
	int to, cost;
};

struct Node {
	int u, dist;

	bool operator > (const Node &oth) const {
		return dist > oth.dist;
	}
};

int N, M;
int dist[NMAX + 1]; // dist[i] = distanta minima de la nodul 1 la nodul 1
bool viz[NMAX + 1];
priority_queue<Node, vector<Node>, greater<Node>> pq;
vector<Edge> adj[NMAX + 1];

int main() {
	fin >> N >> M;

	for(int i = 1; i <= M; i++) {
		int A, B, C;
		fin >> A >> B >> C;

		adj[A].push_back(Edge{B, C});
	}

	for(int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	pq.push({1, dist[1]});

	while(!pq.empty()) {
		int u = pq.top().u, dst = pq.top().dist;
		pq.pop();

		if(dist[u] != dst) {
			continue;
		}

		for(Edge edge: adj[u]) {
			if(dist[edge.to] > dist[u] + edge.cost) {
				dist[edge.to] = dist[u] + edge.cost;
				pq.push({edge.to, dist[edge.to]});
			}
		}
	}

	for(int i = 2; i <= N; i++) {
		if(dist[i] == INF) {
			dist[i] = 0;
		}
		fout << dist[i] << " ";
	}
	return 0;
}