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

using namespace std;

int h[MAX],poz[MAX],a[MAX];
int n,m,nn;
bool l[MAX];
vector<int> szom[MAX],s[MAX];


void percolate(int x){
	int temp;
	
	while(x/2>=1 && a[h[x/2]]>a[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<=n && a[h[2*x]]<a[h[x]])son=2*x;
		
		if(2*x+1<=n && a[h[2*x+1]]<a[h[son]])son=2*x+1;
		
		if(son!=x){
			jo=true;
			
			temp=h[x];
			h[x]=h[son];
			h[son]=temp;
			
			poz[h[x]]=x;
			poz[h[son]]=son;
			
		}
		
		x=son;
		
	}
	
	
}


void dijk(){
	int i;
	nn=n;
	
	while(n>0){
		
		for(i=0;i<szom[h[1]].size();i++){
			
			if(l[szom[h[1]][i]] && a[h[1]]+s[h[1]][i]<a[szom[h[1]][i]]){
				a[szom[h[1]][i]]=a[h[1]]+s[h[1]][i];
				//sift(poz[szom[h[1]][i]]);
				percolate(poz[szom[h[1]][i]]);
			}
		}
		
		l[h[1]]=false;
		h[1]=h[n];
		poz[h[n]]=1;
		n--;
		sift(1);
	
	}
	
	
}



int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	int temp1,temp2,temp3,i;
	
	scanf("%d %d",&n,&m);
	
	
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&temp1,&temp2,&temp3);
		
		szom[temp1].push_back(temp2);
		s[temp1].push_back(temp3);

		
		
	}
	
	for(i=1;i<=n;i++){
	a[i]=inf;
	h[i]=i;
	poz[i]=i;
	l[i]=true;
		
	}
	
	a[1]=0;
	
	dijk();
	
	for(i=2;i<=nn;i++)
		if(a[i]==inf)printf("0 ");else
		printf("%d ",a[i]);
	
	return 0;}