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

int const DMax = 50005;
const int inf = (1 << 30);

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

int N, M;
int D[DMax];
bool InCoada[DMax];
std::vector<std::pair<int, int>>G[DMax];

struct compara {

	bool operator()(int x, int y) {
		return D[x] > D[y];
	}

};


std::priority_queue<int, std::vector<int>, compara> Coada;


void Citeste() {

	fin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back(std::make_pair(y, c));

	}

}

void Dijkstra(int NodStart) {

	for (int i = 1; i <= N; i++)
		D[i] = inf;
	D[NodStart] = 0;
	Coada.push(NodStart);
	InCoada[NodStart] = true;

	while (!Coada.empty()) {

		int NodCurent = Coada.top();
		Coada.pop();
		InCoada[NodCurent] = false;

		for (unsigned int i = 0; i < G[NodCurent].size(); i++) {

			int Vecin = G[NodCurent][i].first;
			int Cost = G[NodCurent][i].second;
			if (D[NodCurent] + Cost < D[Vecin]) {
				D[Vecin] = D[NodCurent] + Cost;
				if (InCoada[Vecin] == false) {
					Coada.push(Vecin);
					InCoada[Vecin] = true;

				}
			}
		}
	}

}


void Afis() {

	for (int i = 2; i <= N; i++)
		if (D[i] != inf)
			fout<< D[i] << " ";
		else fout << "0 ";
}

int main() {

	Citeste();
	Dijkstra(1);
	Afis();

	return 0;
}