#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int MAXN = 50001;
const int MAXM = 50001;
const int INF = 1 << 30;
struct item{
	int val,node;
};
item A[MAXN+MAXM+69]; 
int k;
void swap(int a,int b){
	item X=A[a];
	A[a]=A[b];
	A[b]=X;
}
item mp(int a,int b){
	item u;
	u.val=a;
	u.node=b;
	return u;
}
void upheap(int i){
	if(A[i/2].val>A[i].val){
		swap(i/2,i);
		upheap(i/2);
	}
}
void downheap(int i){
	if( 2*i+1<=k && A[2*i+1].val<A[i].val){
		swap(2*i+1,i);
		downheap(2*i+1);
	}
	else if( 2*i<=k && A[2*i].val<A[i].val){
		swap(2*i,i);
		downheap(2*i);
	}
}
item First(){
	item X=A[1];
	swap(1,k);
	--k;
	downheap(1);
	return X;
}
void Insert(item x){
	A[++k]=x;
	upheap(k);
}
vector<int> G[MAXN],C[MAXN];
int D[MAXN];
int N,M;
int a,b,c;
item u;
int main(){
	in>>N>>M;
	for(int i=1;i<=M;i++){
		in>>a>>b>>c;
		G[a].push_back(b);
		C[a].push_back(c);
	}
	for(int i=2;i<=N;i++) D[i]=INF;
	Insert(mp(0,1));
	while(k>0){
		u=First();
		for(int i=0;i<G[u.node].size();i++){
			if( D[G[u.node][i]] > u.val+C[u.node][i] ){
				D[G[u.node][i]] = u.val+C[u.node][i];
				Insert(mp(D[G[u.node][i]],G[u.node][i]));
			}
		}
	}
	for(int i=2;i<=N;i++) out<<(D[i]==INF?0:D[i])<<' ';
	return 0;
}