#include <iostream>
#include <vector>
#define inf 50000005
#define MAX 50005


using namespace std;

int n,m,dist[MAX],h[MAX],poz[MAX],l=0;

vector<int> szom[MAX],lung[MAX];

void percolate(int x){
	int temp;
	
	
	while(x>1 && dist[h[x/2]]>dist[h[x]]){
		temp=h[x];
		h[x]=h[x/2];
		h[x/2]=temp;
		
		poz[h[x/2]]=x/2;
		poz[h[x]]=x;
		
		x=x/2;
		
	}
	
}

void sift(int x){
	int son=x,temp;
	bool jo=true;
	
	while(jo){
		jo=false;
		son=x;
		
		if(2*x<=l && dist[h[2*x]]<dist[h[x]])son=2*x;
		
		if(2*x+1<=l && dist[h[2*x+1]]<dist[h[son]])son=2*x+1;
		
		if(son!=x){
			temp=h[x];
			h[x]=h[son];
			h[son]=temp;
			
			poz[h[x]]=x;
			poz[h[son]]=son;
			
			jo=true;
			x=son;
		}
		
	}
	
}


void update(int x){
	
	if(x>1 && dist[h[x]]<dist[h[x/2]])percolate(x);
	
	if((2*x<=l && dist[h[x]]>dist[h[2*x]])||(2*x+1<=l && dist[h[x]]>dist[h[2*x+1]]))sift(x);
	
}


int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	int a,b,c,cur,i;
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		
		szom[a].push_back(b);
		lung[a].push_back(c);
		
	}
	
	dist[1]=0;
	cur=1;
	poz[1]=1;
	l++;h[l]=1;
	
	for(i=2;i<=n;i++){dist[i]=inf;l++;h[l]=i;poz[i]=l;}
	
	
	while(l>0){
		
		for(i=0;i<szom[h[cur]].size();i++){
			
			if(dist[szom[h[cur]][i]]>dist[h[cur]]+lung[h[cur]][i]){
				dist[szom[h[cur]][i]]=dist[h[cur]]+lung[h[cur]][i];
				update(poz[szom[h[cur]][i]]);
			}
			
		}
		
		h[poz[cur]]=h[l];
		poz[h[l]]=poz[cur];
		update(poz[cur]);
		l--;
		cur=poz[h[1]];
		
	}
	
	for(i=2;i<=n;i++)
		if(dist[i]==inf)printf("0 ");
	else printf("%d ",dist[i]);
	
	
	return 0;}