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

using namespace std;

#define INPUT "dijkstra.in"
#define OUPUT "dijkstra.out"

#define PINF (1<<30)

struct Muchie {
	int to, cost;
}; 

struct Nod { 
	int valoare;
	friend bool operator<(Nod , Nod );
};

vector<list<Muchie>>muchii;
vector<bool>vizitat;
vector<int>distante;
priority_queue<Nod>heap;
int nrNoduri, nrMuchii;

bool operator<(Nod  n1, Nod n2) {
	return distante[n1.valoare] > distante[n2.valoare];
}


void initAndRead() {
	Muchie aux;
	Nod newNode;

	ifstream in(INPUT);
	in >> nrNoduri;
	muchii.resize(nrNoduri + 3);
	vizitat.resize(nrNoduri + 3, false);
	distante.resize(nrNoduri + 3, PINF);

	in >> nrMuchii;

	for (int i = 0; i < nrMuchii; ++i) {
		int from, to, cost;
		in >> from >> to >> cost;
		aux.to = to;
		aux.cost = cost;
		muchii[from].push_front(aux);
		if (from == 1) {
			distante[to] = cost;
		}
			
	}

	in.close();
}

void dijkstra(int start) {

	Nod newNode;

	for (auto it = muchii[start].begin(); it != muchii[start].end(); ++it) {
		newNode.valoare = it->to;
		heap.push(newNode);
		vizitat[it->to] = true;
	}
	for (int i = 2; i <= nrNoduri; ++i) {
		if (!vizitat[i]) {
			newNode.valoare = i;
			heap.push(newNode);
		}
		else
			vizitat[i] = false;
	}
	distante[start] = 0;
	vizitat[start] = true;

	Nod nodActual;
	while (!heap.empty()) {
		nodActual = heap.top();
		heap.pop();
		int nod = nodActual.valoare;

		//trebuie testata aceasta conditie
		if (distante[nod] == PINF) 
			break;

		for (auto it = muchii[nod].begin(); it != muchii[nod].end(); ++it) {
			if (distante[nod] + it->cost < distante[it->to]) {
				distante[it->to] = distante[nod] + it->cost;
				newNode.valoare = it->to;
				heap.push(newNode);
			}
				
		}
	}

}

void scrieDate() {
	ofstream out(OUPUT);

	for (int i = 2; i < nrNoduri + 1; ++i)
		out << (distante[i] == PINF ? 0 : distante[i]) << " ";

	out << '\n';
	out.close();
}

int main() {

	initAndRead();

	dijkstra(1);

	scrieDate();

	//system("pause");
	return 0;
}