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


const int NMAX = 50002;
const int MMAX = 250002;
const int INF  = INT_MAX;

int dist[NMAX];
struct Compare {

	bool operator()(const int A, const int B) const {
		return dist[A] > dist[B];
	}

};


std::vector< std::pair<int, int> > Graf[NMAX];
std::priority_queue<int, std::vector<int>, Compare> PrCoada;


bool viz[NMAX];

void init_dist(int N) {

	for (int i = 1; i <= N; ++i) {
		dist[i] = INF;
	}

}





int main() {

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


	int N, M;
	in >> N >> M;

	for (int i = 1; i <= M; ++i) {
		int nod1, nod2, cost;
		in >> nod1 >> nod2 >> cost;

		Graf[nod1].push_back(std::make_pair(nod2, cost));
	}

	int radacina = 1;
	init_dist(N);
	dist[radacina] = 0;

	PrCoada.push(radacina);

	while (!PrCoada.empty()) {

		int nod_curent = PrCoada.top();
		PrCoada.pop();
		viz[nod_curent] = false;
		
		for (int i = 0; i < Graf[nod_curent].size(); ++i) {

			int Vecin = Graf[nod_curent][i].first;
			int Cost = Graf[nod_curent][i].second;

			if (dist[nod_curent] + Cost < dist[Vecin]) {
				dist[Vecin] = dist[nod_curent] + Cost;

				if (!viz[Vecin]) {
					viz[Vecin] = true;
					PrCoada.push(Vecin);
				}
			}
		}


	}

	for (int i = 2; i <= N; ++i) {
		if (dist[i] == INT_MAX) {
			out << 0 << ' ';
		}
		else {
			out << dist[i] << ' ';
		} 
	}

	system("PAUSE");
	return 0;
}