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


using namespace std;

vector<int> szom[MAX],cost[MAX];
int n,m,k=0;
int h[MAX],poz[MAX],d[MAX];

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


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


void dijk(){
	int i,min,temp;
	
	for(i=1;i<=n;i++){poz[i]=-1;d[i]=inf;}
	
	k++;
	h[1]=1;poz[1]=1;d[1]=0;
	
	while(k){
		min=h[1];
		
		h[1]=h[k];
		k--;poz[h[1]]=1;
		sift(1);
		
		temp=szom[min].size();
		for(i=0;i<temp;i++){
		
			if(d[min]+cost[min][i]<d[szom[min][i]]){

				d[szom[min][i]]=d[min]+cost[min][i];
				
				if(poz[szom[min][i]]==-1){
					
					k++;
					h[k]=szom[min][i];
					poz[szom[min][i]]=k;
					percolate(k);
					
				}else{
					
					percolate(poz[szom[min][i]]);
				}

			}				
		}
		
		
	}
	
	
}


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