#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int n, m;
	fin >> n >> m;
	int u, v, w;
	vector<pair<int,int> > adjl[n+1];
	vector<pair<int,int> >::iterator it;
	for (; m > 0; --m) {
		fin >> u >> v >> w;
		adjl[u].push_back(pair<int,int>(w,v));
	}

	const int inf = 1e6;
	vector<int> dist(n+1, inf);
	dist[1] = 0;
	vector<pair<int,int> > pq;
	pq.push_back(pair<int,int>(0,1));
	while (!pq.empty()) {
		w = pq.front().first;
		u = pq.front().second;
		pop_heap(pq.begin(), pq.end(), greater<pair<int,int> >());
		pq.pop_back();
		if (dist[u] != w) continue;
		for (it = adjl[u].begin(); it != adjl[u].end(); ++it) {
			v = it->second;
			if (dist[v] > w + it->first) {
				dist[v] = w + it->first;
				pq.push_back(pair<int,int>(dist[v],v));
				push_heap(pq.begin(), pq.end(), greater<pair<int,int> >());
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		fout << (dist[i] == inf? 0 : dist[i]) << ' ';
	return 0;
}