#include <fstream>
#include <iterator>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

#define oo (1 << 30)

vector <int> d;
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > H;
vector <list <pair <int, int> > > g;

int n, m;

template <typename T>
class Write {
	public: 
	void operator() (T x) {
		fout << ((x == oo) ? 0 : x) << " ";
	}
};

int main() {
	fin >> n >> m;
	d.resize(n+1, oo);
	g.resize(n+1);
	while (m--) {
		int x, y, c;
		fin >> x >> y >> c;
		g[x].push_back (make_pair (c, y));
	}
	fin.close();
	H.push(make_pair(0,1));
	while (H.size()) {
		pair <int, int> x = H.top();
		H.pop();
		if (d[x.second] != oo)
			continue;
		d[x.second] = x.first;
		for (list <pair <int, int> > :: iterator i = g[x.second].begin(); i != g[x.second].end(); ++i)
			if (d[(*i).second] == oo)
				H.push (make_pair ((*i).first + x.first, (*i).second));
	}
	for_each (d.begin()+2, d.end(), Write<int>());
	fout.close();
}