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