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

#define NMax 100005
#define inf (1<<30)+100
#define pb push_back
#define mp make_pair

using namespace std;

struct cmp {
	bool operator() (pair<int, int> a, pair<int, int> b) {
		return (a.first > b.first);
	}
};

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

int n, m;
vector<int> V[NMax];
vector<int> C[NMax];
int dist[NMax];
priority_queue<pair<int, int>, vector< pair<int, int> >, cmp> Q;

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

	for (int i=2;i<=n;i++)
		dist[i] = inf;
	dist[1] = 0;
}

void solve() {
	Q.push(mp(0,1));
	while (!Q.empty()) {
		int nod = Q.top().second;
		int cost = Q.top().first;
		Q.pop();

		for (unsigned i=0;i<V[nod].size();i++) {
			if (cost + C[nod][i] < dist[V[nod][i]]) {
				dist[V[nod][i]] = cost + C[nod][i];
				Q.push(mp(dist[V[nod][i]], V[nod][i]));
			}
		}
	}
}

void print() {

	for (int i=2;i<=n;i++)
		g<<((dist[i] == inf)?0:dist[i])<<' ';
}

int main() {

	read();
	solve();
	print();

	f.close(); g.close();
	return 0;
}