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