/*
	Bellman-Ford-Moore algorithm.
*/

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

using namespace std;

#define N 50001
#define oo 0x3f3f3f3f

int n, m, d[N], f[N], in_queue[N];
queue<int> q;
vector<pair<int, int> > L[N];

void init() {
	for (int i=1; i<=n; i++) {
		d[i]=oo;
		in_queue[i]=0;
	}
	d[1]=0;
}

void BellmanFordMoore() {
	q.push(1); // push source in deque
	in_queue[1]=1;

	while (!q.empty()) {
		int v=q.front();
		q.pop();
		in_queue[v]=0;
		
		for (int j=0; j<L[v].size(); j++) {
			int w=L[v][j].first;
			int c=L[v][j].second;
		
			// relax edge
			if (d[w]>d[v]+c) {
				d[w]=d[v]+c;
				f[w]=v;
					
				// maintaint edges in deque whose distance have changed
				if (!in_queue[w]) {
					in_queue[w]=1;
					q.push(w);
				}
			}
		}
	}
}

void showDistances() {
	for (int i=2; i<=n; i++)
		cout<<(d[i] < oo ? d[i] : 0)<<" ";
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	// number of nodes
	cin>>n;

	// number of edges
	cin>>m;

	for (int i=1; i<=m; i++) {
		int x, y, c;

		cin>>x>>y>>c;
		L[x].push_back(make_pair(y, c));
	}
	
	init();

	BellmanFordMoore();

	showDistances();

	return 0;
}