#include <iostream>
#include <fstream>
#include <set>
#include <vector>

#define MAXN 50010
#define MAXM 250100
#define INF 1000000000

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

int N,M;
struct Edge {
	int at;
	int cost;
};
struct Node {
	int dist;
	vector<Edge> Adj;
};
Node V[MAXN];
struct CompareNodes {
	bool operator() (const int& A, const int& B) const {
		return V[A].dist <= V[B].dist;
	}
};
set<int,CompareNodes> s;

void read_f() {
	int i,x,y,c;
	Edge tmp;
	fin >> N >> M;
	for (i=0;i<M;++i) {
		fin >> x >> y >> c;
		x -= 1;
		y -= 1;
		tmp.at = y;
		tmp.cost = c;
		V[x].Adj.push_back(tmp);
	}
	for (i=0;i<N;++i) V[i].dist = INF;
	V[0].dist = 0;
	s.insert(0);
	fin.close();
}

void dump_set() {
	set<int,CompareNodes>::iterator it;
	for (it = s.begin(); it != s.end(); ++it) {
		cout << *it << " ";
	}
	cout << "\n";
	for (it = s.begin(); it != s.end(); ++it) {
		cout << V[*it].dist << " ";
	}
	cout << "\n";
}

void dijktra() {
	int x,i;
	while (!s.empty()) {
		x = *s.begin();
		s.erase(s.begin());
		for (i=0;i<V[x].Adj.size();++i) {
			if (V[V[x].Adj[i].at].dist > V[x].dist + V[x].Adj[i].cost) {
				V[V[x].Adj[i].at].dist = V[x].dist + V[x].Adj[i].cost;
				s.insert(V[x].Adj[i].at);
			}
		}
	}
}

void write_f() {
	int i;
	for (i=1;i<N;++i)
		fout << ((V[i].dist >= INF)?0:V[i].dist) << " ";
	fout << "\n";
	fout.close();
}

int main() {
	read_f();
	dijktra();
	write_f();
	return 0;
}