/*
	Bellman-Ford-Moore algorithm.
*/

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

#define N 1000
#define oo 0x3f3f3f3f

int n, m, d[N], f[N], in_deque[N];
deque<int> dq;
vector<pair<int, int> > L[N];

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

inline void relaxEdge(int v, int w, int c) {
	if (d[w]>d[v]+c) {
		d[w]=d[v]+c;
		f[w]=v;
	}		
}

void BellmanFordMoore() {
	dq.push_back(1); // push source in deque
	in_deque[1]=1;

	while (!dq.empty()) {
		int v=dq.front();
		dq.pop_front();
		in_deque[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_deque[w]) {
					in_deque[w]=1;
					dq.push_back(w);
				}
			}
		}
	}
}

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

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;
}