#include <cstdio>
#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)

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

	vector<int> Q(N+1);
	int bq = 0, eq = 0;
	Q[eq++] = S;
	vector<bool> inq(N+1, 0);
	inq[S] = 1;

	while (bq != eq) {
		int u = Q[bq++];
		inq[u] = 0;
		if (bq > N)
			bq -= N;
	      
		tr(G[u], vv) {
			int v = vv->first;
			if ((!D[v]) || (D[u] + vv->second < D[v])) {
				D[v] = D[u] + vv->second;
				if (!inq[v]) {
					Q[eq++] = v;
					if (eq > N)
						eq -= N;
					inq[v] = 1;
				}
					
			}
		}
	}
}

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

	FILE *fi = fopen("dijkstra.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	G.resize(N+1);
	while (M--) {
		fscanf(fi, "%d %d %d", &u, &v, &w);
		G[u].pb(pii(v, w));
	}
	fclose(fi);

	dijkstra(1, D);

	FILE *fo = fopen("dijkstra.out", "w");
	for (vector<int>::const_iterator ii = D.begin()+2; ii != D.end(); ++ii)
		fprintf(fo, "%d ", *ii);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}