#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

typedef pair <int, int> PII;
#define MP make_pair

const int NMAX = 1 << 16;
const int INF = 0x3f3f3f3f;

bool V[NMAX];
int N, M, D[NMAX];
vector <PII> G[NMAX];
priority_queue <PII> H;

void read(void) {
	FILE *fin = fopen("dijkstra.in", "rt");
	int i, a, b, c;

	fscanf(fin, " %d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d %d", &a, &b, &c);
		G[a].push_back( MP(c, b) );
	}

	fclose(fin);
}

void dijkstra(void) {
	int u, c;
	vector <PII> :: iterator v;

	memset(D, 0x3f, sizeof(D));
	D[1] = 0;
	H.push( MP(0, 1) );
	
	while (!H.empty()) {

		while (!H.empty() && V[H.top().second] == true)
			H.pop();

		if (H.empty()) break;

		c = H.top().first;
		u = H.top().second;
		H.pop(); V[u] = true;

		for (v = G[u].begin(); v != G[u].end(); ++v)
			if (c + v->first < D[v->second]) {
				D[v->second] = c + v->first;
				H.push( MP(D[v->second], v->second) );
			}
	}
}

void write(void) {
	FILE *fout = fopen("dijkstra.out", "wt");
	int i;

	for (i = 2; i <= N; ++i)
		fprintf(fout, "%d ", D[i] == INF ? 0 : D[i]);
	fprintf(fout, "\n");

	fclose(fout);
}

int main(void) {

	read();

	dijkstra();

	write();

	return 0;
}