#include <fstream>
#include <vector>
#include <queue>
#define DIM 50005
#define INF 2000000000
#define vint vector< pair<int, int> >::iterator
#define infile "dijkstra.in"
#define outfile "dijkstra.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.first > b.first;
	}
};

vector< pair<int, int> > L[DIM];

int n, m, a, b, c;

int D[DIM];

bool ok[DIM];

priority_queue<pair<int, int>, vector< pair<int, int> >, cmp> H;

int main() {
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> a >> b >> c;
		L[a].push_back(make_pair(b, c));
	}
	for (int i = 2; i <= n; ++i)
		D[i] = INF;
	H.push(make_pair(0, 1));
	while (!H.empty()) {
		while (!H.empty() && ok[H.top().second])
			H.pop();
		if (H.empty())
			break;
		int nod = H.top().second;
		ok[nod] = 1;
		D[nod] = H.top().first;
		for (vint it = L[nod].begin(); it != L[nod].end(); ++it)
		if (D[it->first] > D[nod] + it->second)
			H.push(make_pair(D[nod] + it->second, it->first));
	}
	for (int i = 2; i <= n; ++i)
		g << (D[i] == INF ? 0 : D[i]) << " ";
	return 0;
}

//This room. This bullet. There's a bullet for everyone. And a time. And a place. Yes... maybe this is how it has to be. - 47