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

using namespace std;

#define pb push_back
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

const int oo = 1<<30;

typedef pair<int, int> pii;

int N;
vector< vector<pii> > G;
vector<int> D;

void dijkstra(int S, vector<int> &D) {
	D.resize(N+1);
	fill(D.begin(), D.end(), oo);

	priority_queue< pii, vector<pii>, greater<pii> > Q;
	Q.push(pii(0, S));
	D[S] = 0;

	vector<bool> viz(N+1, false);

	while (!Q.empty()) {
		while (!Q.empty() && viz[Q.top().second])
			Q.pop();
		if (Q.empty())
			break;

		int u = Q.top().second;
		int d = Q.top().first;
		Q.pop();
		viz[u] = true;

		tr(G[u], vv) {
			int v = vv->first;
			if (D[u] + vv->second < D[v]) {
				D[v] = D[u] + vv->second;
				Q.push(pii(D[v], v));
			}
		}
	}
}

int main(int argc, char *argv[]) {
	int M, u, v, w;

	ifstream fin("dijkstra.in");
	fin >> N >> M;
	G.resize(N+1);
	while (M--) {
		fin >> u >> v >> w;
		G[u].pb(pii(v, w));
	}
	fin.close();

	dijkstra(1, D);

	ofstream fout("dijkstra.out");
	for (vector<int>::const_iterator ii = D.begin()+2; ii != D.end(); ++ii)
		fout << (*ii == oo ? 0 : *ii) << " ";
	fout << endl;
	fout.close();

	return 0;
}