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

#define pii pair<int,int> //sa nu scriem prea mult
#define INFINIT 10000000

using namespace std;

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

int main() {

	//Dijsktra

	//algoritmul Dijskstra se foloseste pentru a determina drumul cel mai scurt de la un nod (1 in cazul nostru) la toate celelalte noduri

	//E un algoritm greedy, presupune ca distanta[1] = 0 , si distanta celorlalte e infinit

	//Adaugam pereche distanta,nod intr-o coada de prioritati Min Heap (scoatem cel mai mic element din ea -- cu cea mai mica distanta)

	//Scoatem din coada elementul curent, si relaxam vecinii lui


	priority_queue<pii, vector<pii>, greater<pii>> coada; // tinem in coada perechi {cost,nod}

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

	vector<vector<pii>> vecini(n+1); // tinem pt fiecare nod vector de {vecin,cost}

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


	vector<int> distante(n + 1, INFINIT); // nod-distanta

	//initializem coada de prioritati si distantele

	distante[1] = 0;

	for (int i = 1; i <= n; i++) {
		coada.push({ distante[i], i});
	}

	//coada de prioritati e  sortata dupa distante

	while (!coada.empty()) {
		pii pereche_curenta = coada.top();
		int nod_curent = pereche_curenta.second;
		coada.pop();

		// studiem vecinii si vedem daca putem relaxa
		for (auto v : vecini[nod_curent]) { // second - a doua variabila - e numele nodului
			//daca distanta nod curent + cost pana la vecin < distanta vecin , relaxam
			if (distante[nod_curent] + v.second < distante[v.first]) {
				distante[v.first] = distante[nod_curent] + v.second;
			}
		}
	}

	for (int i = 2; i <= n; i++) {

		if (distante[i] == INFINIT) {
			fout << "0 ";
		}
		else {
			fout << distante[i] << ' ';
		}
	}

	return 0;
}