#include<stdio.h>
#include<vector>
#define inf 2000000000
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
using namespace std;
int n,m,k,i,x,y,z,j,heapn;
int minim,p;
int s[50001],dest[50001],mymin[50001];
pair<int,int> d[50001]; //first=cost,second=dest
vector< pair<int,int> > a[50001]; //first=dest,second=cost

void downheap(int p){
	int l,r;
	while(2*p<=heapn){
		minim=p;
		l=2*p;
		r=2*p+1;
		if(d[minim].first>d[l].first)
			 minim=l;
		if(r<=heapn&&d[minim].first>d[r].first)
			 minim=r;
		if(minim!=p){
			 pair<int,int> t=d[p];
						   d[p]=d[minim];
						   d[minim]=t;
				int x=dest[d[p].second];
			    dest[d[p].second]=dest[d[minim].second];
			    dest[d[minim].second]=x;
		}
		else break;
	}
}

void upheap(int p){
	int t;
	while(p>1){
		t=p/2;
		if(d[p].first<d[t].first){
			pair<int,int> m=d[p];
						  d[p]=d[t];
						  d[t]=m;
			int x=dest[d[p].second];
			    dest[d[p].second]=dest[d[t].second];
			    dest[d[t].second]=x;
			p=t;
		}
	  else break;
	}
}

int main(){
//citire
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
	fscanf(f,"%d%d%d",&x,&y,&z);
	a[x].push_back(make_pair(y,z));
	}


//d=inf,mymin=inf,dest=0
for(i=0;i<=n;i++){
	d[i].first=inf;
	mymin[i]=inf;
	dest[i]=0;
}

//d[i] = distanta de la nod[1] la nod[i]
for(i=0;i<=(int)a[1].size()-1 ;i++){
	heapn++;
	d[heapn].first=a[1][i].second;
	d[heapn].second=a[1][i].first;
	dest[a[1][i].first]=heapn;
	upheap(heapn);
}

//selectam primul nod
s[1]=1;

//rezolvare Nlog(N)
while(heapn){
    p=d[1].second;
	int cost=d[1].first;
	//stergem primul element si reactualizam heapul
	d[1]=d[heapn];
	heapn--;
	dest[d[1].second]=1;
	downheap(1);
	//salvam costul minim pentru nodul eliminat
	  if(mymin[p]>cost)
		  mymin[p]=cost;
                   
 s[p]=1;
 //minimul pana la toti vecinii
  for(i=0;i<=(int)a[p].size()-1;i++)
	  //daca vecinul nu a fost selectat si costul este mai mic
	  if(s[a[p][i].first]==0 && cost +a[p][i].second < d[dest[a[p][i].first]].first ){
		  //daca vecinul exista in heap
		  if(dest[a[p][i].first]!=0)
	         d[dest[a[p][i].first]].first=cost+a[p][i].second;
		  //daca nu, il adaugam
		  else {
			   heapn++;
			   d[heapn].first=cost+a[p][i].second;
			   d[heapn].second=a[p][i].first;
			   dest[a[p][i].first]=heapn;
			   upheap(heapn);
		  }	
     if(mymin[a[p][i].first] > cost+a[p][i].second) 
		   mymin[a[p][i].first] = cost+a[p][i].second;
	  }
dest[p]=-1;
}


//afisam
for(i=2;i<=n;i++){
	if(mymin[i]!=inf)
	fprintf(g,"%d ",mymin[i]);
	else fprintf(g,"%d ",0);
}
return 0;
}