#include <fstream>
#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, vector <PII>, greater<PII> > H;

void read(void) {
	ifstream fin("dijkstra.in");
	int i, a, b, c;

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

	fin.close();
}

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) {
	ofstream fout("dijkstra.out");
	int i;

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

	fout.close();
}

int main(void) {

	read();

	dijkstra();

	write();

	return 0;
}