#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define INFINIT 10000000

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

struct vecin {
	int nod, cost;
};

int main() {
	//DIJSKTRA pe graf orientat ponderat

	int n, m;
	fin >> n >> m;

	vector<vector<vecin>> vecini(n + 1);

	for (int i = 1; i <= m; i++) {
		int x, y, z;
		fin >> x >> y >> z;
		vecini[x].push_back({ y,z }); // x are vecinul y cu costul z
	}

	vector<bool> vizitat(n + 1, false);
	vector<int> distanta(n + 1, INFINIT);
	distanta[1] = 0; // calculam distanta de la nodul 1 la celelalte

	//parcurgem N noduri
	for (int i = 1; i <= n; i++) {

		//cautam nodul NEVIZITAT cu distanta minima
		int nod = -1;
		int dist = INFINIT;

		for (int j = 1; j <= n; j++) {
			if (distanta[j] < dist && !vizitat[j]) {
				nod = j;
				dist = distanta[j];
			}
		}

		if (nod == -1 || dist == INFINIT) break;

		//procesam NOD : il marcam ca vizitat
		vizitat[nod] = true;

		//procesam si relaxam vecinii lui daca e cazul
		for (auto v : vecini[nod]) {
			if (distanta[nod] + v.cost < distanta[v.nod]) {
				distanta[v.nod] = distanta[nod] + v.cost;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (distanta[i] == INFINIT) {
			distanta[i] = 0;
		}
	}

	for (int i = 2; i <= n; i++) {
		fout << distanta[i] << ' ';
	}
}