#include <queue>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
vector<pair<int, int>> g[50001];
int d[50001];
int v[50001];
void dijk(){
	int x;
	d[1] = 0;
	v[1] = 1;
	queue<pair<int,int>> q;
	q.push(pair<int, int>(1,0));
	while (!q.empty()){
		x = q.front().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;
			if (!v[i.first]){
				q.push(make_pair(i.first, d[i.first]));
				v[i.first] = 1;
			}
		}
	}
}
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(pair<int, int>(b, c));
	}
	for (int i = 2; i <= N; ++i)d[i] = 200000000;
	d[1] = 0;
	dijk();
	for (int i = 2; i <= N; ++i)
	if (d[i] == 200000000)of << 0 << " ";
	else
		of << d[i] << " ";
}