#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int inf = 1<<29;

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int n, m;
	fin >> n >> m;
	vector<ii> adjl[n+1];
	for (int i=0, u, v, e; i<m; ++i) {
		fin >> u >> v >> e;
		adjl[u].push_back( ii(e, v) );
	}
	vi dist(n+1, inf);
	dist[1] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push( ii(0, 1) );

	while (!pq.empty()) {
		int v = pq.top().second, d = pq.top().first;
		pq.pop();
		if (d == dist[v]) {
			for (vector<ii>::iterator it = adjl[v].begin(); it != adjl[v].end(); ++it) {
				int v2 = it->second;
				if ( dist[v2] > dist[v] + it->first ) {
					dist[v2] = dist[v] + it->first;
					pq.push(ii( dist[v2], v2 ));
				}
			}
		}
	}
	for (int i=2; i<=n; ++i) fout << (dist[i]==inf ?0 :dist[i]) << ' ';
	return 0;
}