#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 5e4+10;
const int inf = 0x3F3F3F3F;
int n,m;
vector<vector<pair<int,int>>> mat(nmax);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
vector<int> distante(nmax);
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,cost;
	for(int i = 1; i <=m;i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1].push_back(make_pair(cost,nod_2));
	}
};
void dijkstra(){
	fill(distante.begin(),distante.end(),inf);
	distante[1] = 0;
	pq.push(make_pair(0,1));
	while(!pq.empty()){
		pair<int,int> nod = pq.top();
		pq.pop();
		if(distante[nod.second] < nod.first){
			continue;
		};
		for(auto nod_aux : mat[nod.second]){
			if(distante[nod_aux.second] > nod_aux.first + nod.first){
				distante[nod_aux.second] = nod_aux.first + nod.first;
				pq.push(make_pair(distante[nod_aux.second],nod_aux.second));
			}
		}
	};
	for(int i = 2; i <=n; i++){
		fout << (distante[i] == inf ? 0 : distante[i]) << " ";
	}
}
int main(){
	read_input();
	dijkstra();
	return 0;
}