#include <set>
#include <fstream>
#include <vector>
using namespace std;
set<pair<int, int>> q;
vector<pair<int,int>> g[50001];
int d[50001];
void dijk(){
	q.insert(make_pair(0, 1));
	while (!q.empty()){
		int x = q.begin()->second;
		q.erase(q.begin());
		for (const auto& i : g[x])
			if (d[i.second] > d[x] + i.first){
				d[i.second] = d[x] + i.first;
				q.insert(make_pair(d[i.second], i.second));
			}
	}
}
int main(){
	ifstream f("dijkstra.in");
	ofstream of("dijkstra.out");
	int a, b, c,N,M;
	f >> N >> M;
	for (int i = 0; i < M; ++i){
		f >> a >> b >> c;
		g[a].push_back(make_pair(c, b));
	};
	for (int i = 2; i <= N; ++i)d[i] = 2000000000;
	d[1] = 0;
	dijk();
	for (int i = 2; i <= N; ++i)
	if (d[i] == 2000000000)of <<"0 ";
		else
			of << d[i] << " ";
	return 0;
}