#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];


struct graf
{
    int nod, cost;
    graf *next;
};

graf *a[MAX];

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
void percolate(int x){
	int temp;
	
	
	while(x/2>=1 && d[h[x/2]]>d[h[x]]){
		temp=h[x];
		h[x]=h[x/2];
		h[x/2]=temp;
		poz[h[x]]=x;
		poz[h[x/2]]=x/2;
		x/=2;
	}
	
	
	
}


void sift(int x){
	int son=x,temp;
	bool jo=true;
	
	while(jo){
		son=x;
		jo=false;
		
		if(2*x<=k && d[h[2*x]]<d[h[x]])son=2*x;
		
		if(2*x+1<=k && d[h[2*x+1]]<d[h[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 min,temp;
	int i;
	
	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();
		
		graf *q=a[min];
		while(q){
		
			if(d[min]+q->cost<d[q->nod]){

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

			}
			q=q->next;
		}
		
		
	}
	
	
}


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);
		add(temp1,temp2,temp3);
	}
	
	dijk();
	
	for(i=2;i<=n;i++)
		if(d[i]==inf)printf("0 ");else
		printf("%d ",d[i]);
	
	
return 0;}