#include<fstream>
#include<vector>
#define NMAX 50002
#define inf 400000000
using namespace std;
int n,m,D[NMAX],N,H[NMAX],i,j,poz[NMAX],minu,nod;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair <int,int > >G[NMAX];
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));
	}
}
int rs(int k){
	return 2*k+1;
}
int ls(int k){
	return 2*k;
}
void init(){
	for(int i=2;i<=n;i++)
		D[i]=inf;
	H[++N]=1;
	poz[1]=1;
}
void percolate(int k){
	while(k>1  && D[H[k]]<D[H[k/2]]){
		swap(poz[H[k]],poz[H[k/2]]);
		swap(H[k],H[k/2]);
		k/=2;
	}
}
void sift(int k){
	int son=k;
	if(ls(k)<=N && D[H[ls(k)]]<D[H[son]])
		son=ls(k);
	if(rs(k)<=N  && D[H[rs(k)]]<D[H[son]])
		son=rs(k);
	if(son!=k){
		swap(poz[H[k]],poz[H[son]]);
		swap(H[k],H[son]);
		sift(son);
	}
}
void  minim (int &minu){
	minu=H[1];
	H[1]=H[N--];
	poz[H[1]]=1;
	sift(1);
}
void insert(int x){
	H[++N]=x;
	poz[x]=N;
	percolate(poz[x]);
}
void dijkstra(){
	for(;N;){
		minim(minu);
		nod=minu;
		for(int i=0;i<G[nod].size();++i){
			if(D[G[nod][i].first]>D[nod]+G[nod][i].second)
				D[G[nod][i].first]=D[nod]+G[nod][i].second;
			if(poz[G[nod][i].first])
				percolate(poz[G[nod][i].first]);
			else
				insert(G[nod][i].first);
		}
	}
}
void afisare(){
	for(i=2;i<=n;i++)
		if(D[i]==inf)
			g<<0<<" ";
		else
			g<<D[i]<<" ";
}
int main (){
	citire();
	init();
	dijkstra();
	afisare();
	return 0;
}