#include <bits/stdc++.h>

using namespace std;

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

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

int N, M;

struct Edge {
	int from, to, cost;
};

vector<Edge> edges;
int dist[NMAX + 1];

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

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

		edges.push_back(Edge{A, B, C});
	}

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

	bool any = 1;

	while(any) {
		any = 0;
		for(Edge edge: edges) {
			if(dist[edge.to] > dist[edge.from] + edge.cost) {
				any = 1;
				dist[edge.to] = dist[edge.from] + edge.cost;
			}
		}
	}

	// COMPLEXITATE TIMP: O(N * M)

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