#include <iostream>
#include <fstream>
#include <vector>
#include <set>

#define NMax 50001
#define inf (1<<30)
#define mp make_pair

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m;
vector<int> V[NMax];
vector<int> C[NMax];
int cost[NMax];
set<pair<int, int> > q;

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a, b, p;
		f>>a>>b>>p;
		V[a].push_back(b);
		C[a].push_back(p);
	}
}

void solve() {
	for (int i=1;i<=n;i++)
		cost[i] = inf;
	cost[1] = 0;
	q.insert(q.begin(), mp(0, 1));

	while (!q.empty()) {
		pair<int, int> ex = *(q.begin());
		int c = ex.first;
		int node = ex.second;
		q.erase(q.begin());

		for (int i=0;i<V[node].size();i++) {
			int vecin = V[node][i];
			if (cost[vecin] > c + C[node][i]) {
				cost[vecin] = c+C[node][i];
				q.insert(q.end(), mp(cost[vecin], vecin));
			}
		}
	}
}

void output() {
	for (int i=2;i<=n;i++)
		if (cost[i] == inf)
			g<<0<<' ';
		else
			g<<cost[i]<<' ';
}

int main() {

	read();
	solve();
	output();

	f.close();
	g.close();

	return 0;
}