#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50002
#define inf 400000000
using namespace std;
int D[NMAX],n,m,i;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair< int,int > >G[NMAX];
queue<int>coada;
void citire(){
	f>>n>>m;
	int x,y,c;
	for(i=1;i<=m;i++){
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
}
void dijkstra (){
	for(i=2;i<=n;i++)
		D[i]=inf;
	coada.push(1);
	D[1]=0;
	int x;
	while(!coada.empty()){
		x=coada.front();coada.pop();
		for(int i=0;i<G[x].size();++i){
			if(D[G[x][i].first]>D[x]+G[x][i].second){
				D[G[x][i].first]=D[x]+G[x][i].second;
			    coada.push(G[x][i].first);
			}
		}
	}
}
void afisare(){
	for(i=2;i<=n;i++){
		if(D[i]==inf)
			g<<0<<" ";
		else
			g<<D[i]<<" ";
	}
}
int main (){
	citire();
	dijkstra();
	afisare();
	return 0;
}