#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

#define PINF (1<<30)

struct Muchie {
	int to, cost;
};

vector<Muchie>muchii[50002];
queue<int>Q;
bitset<50002>InQ;
vector<int>distante(50002,PINF);
int nrNoduri, nrMuchii;



void initAndRead() {
	Muchie aux;

	ifstream in(INPUT);
	in >> nrNoduri;

	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_back(aux);
	}

	in.close();
}

void dijkstra(int start) {

	distante[start] = 0;
	Q.push(start);
	InQ[start] = 1;

	while (!Q.empty()) {
		int nod = Q.front();
		Q.pop();

		InQ[nod] = 0;

		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;
				if (!InQ[it->to]) {
					Q.push(it->to);
					InQ[it->to] = 1;
				}
		
			}

		}
	}

}

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();

	return 0;
}