#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;
};

int N, M;
int dist[NMAX + 1]; // dist[i] = distanta minima de la nodul 1 la nodul 1
bool viz[NMAX + 1];
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;

	for(int i = 1; i <= N; i++) {
		int u = -1;
		for(int j = 1; j <= N; j++) {
			if(!viz[j] && (u == -1 || dist[j] < dist[u])) {
				u = j;
			}
		}

		if(u == -1 || dist[u] == INF) {
			break;
		}

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

	// O(N^2 + M)

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