#include <bits/stdc++.h>
#define NMax 50005
#define inf 1<<30

#define pb push_back
#define mp make_pair
using namespace std;

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

struct cmp {
	bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
		if (a.first < b.first)
			return false;
		if (a.first == b.first && a.second < b.second)
			return false;
		return true;
	}
};

int n, m;
int R[NMax];
vector<int> V[NMax];
vector<int> C[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);
	}
}

void dijkstra() {
	for (int i=2;i<=n;i++)
		R[i] = inf;
	R[1] = 0;
	
	q.push(mp(0, 1));
	while (!q.empty()) {
		pair<int, int> el = q.top();
		int nod = el.second;
		int cost = el.first;
		q.pop();
		
		for (unsigned i = 0; i < V[nod].size();i++) {
			int vecin = V[nod][i];
			int muchie = C[nod][i];
			
			if (R[vecin] > muchie + cost) {
				R[vecin] = muchie + cost;
				q.push(mp(R[vecin], vecin));
			}
		}
	}
}

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

int main() {
	
	read();
	dijkstra();
	output();
	
	f.close(); g.close();
	return 0;
}