#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <fstream>
#include <climits>

using namespace std;

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

const int INF = INT_MAX;

struct vecinCost {
	int y;
	int cost;
};

typedef pair<int, int> distantaNod;

int distanta[51000];
int vis[51000];
vector<vecinCost> lista[251000];
priority_queue<distantaNod> PQ;

int main() {
	// Optimizare pentru viteza I/O (recomandata la probleme cu input mare)
	ios_base::sync_with_stdio(false);
	fin.tie(NULL);

	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int xC, yC, costC;
		fin >> xC >> yC >> costC;

		vecinCost curent;
		curent.y = yC;
		curent.cost = costC;

		lista[xC].push_back(curent);
	}

	distanta[1] = 0;
	for (int i = 2; i <= n; i++)
		distanta[i] = INF;

	// PQ este MaxHeap implicit. Folosim minus pentru a simula MinHeap.
	PQ.push({ -distanta[1], 1 });

	while (!PQ.empty()) {
		int nod = PQ.top().second;

		PQ.pop();

		if (vis[nod] == 1) {
			continue;
		}

		vis[nod] = 1;

		for (auto nodIterator : lista[nod]) {
			int vecin = nodIterator.y;
			int cost = nodIterator.cost;

			// Verificam sa nu facem overflow la adunare (desi cu int e ok aici, e bine sa verificam != INF)
			if (distanta[nod] != INF && distanta[vecin] > distanta[nod] + cost) {
				distanta[vecin] = distanta[nod] + cost;
				PQ.push({ -distanta[vecin], vecin });
			}
		}
	}

	for (int i = 2; i <= n; i++)
		if (distanta[i] == INF) {
			fout << 0 << " ";
		}
		else {
			fout << distanta[i] << " ";
		}

	return 0;
}