#include<fstream>
#include<limits.h>
#define inf INT_MAX
#include<vector>
#define lim 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int H[lim],Pos[lim],D[lim],n,N,nod,minu,y,c,x,m;
vector< pair < int,int > >G[lim];
inline int rs(int nod){
	return 2*nod+1;
}
inline int ls(int nod){
	return 2*nod;
}
void percolate(int k){
	while(k>1 && D[H[k]]<D[H[k/2]]){
		swap(Pos[H[k]],Pos[H[k/2]]);
		swap(H[k],H[k/2]);
		k/=2;
	}
}
void sift(int k){
	int son=k;
	if(k<=N && D[H[ls(k)]]<D[H[son]])
		son=ls(k);
	if(k<=N && D[H[son]] <D[H[rs(k)]])
		son=rs(k);
	if(son!=k){
		swap(Pos[H[k]],Pos[H[son]]);
		swap(H[k],H[k/2]);
		sift(son);
	}
}
void insert(int X){
	H[++N]=X;
	Pos[X]=N;
	percolate(Pos[X]);
}
void getmin(){
	minu=H[1];
	H[1]=H[N];
	N--;
	sift(1);
}
int main (){
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	for(int i=2;i<=n;i++)
		D[i]=inf;
	Pos[1]=1;
	H[1]=1;
	++N;
	for(;N;){
		getmin();
		nod=minu;
		for(int i=0;i<G[nod].size();++i){
			if(D[G[nod][i].first]>D[nod]+D[G[nod][i].second])
				D[G[nod][i].first]=D[nod]+D[G[nod][i].second];
			if(Pos[G[nod][i].first])
				percolate(Pos[G[nod][i].first]);
			else
				insert(G[nod][i].first);
		}
	}
	for(int i=2;i<=n;i++)
		if(D[i]!=inf)
			g<<D[i]<<" ";
		else
			g<<"0 ";
	return 0;
}