#include<fstream>
#include<vector>
#define inf 2000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,k,i,x,y,z,j,heapn,where,cat;
int minim,p;
int dest[50011],mymin[50011];
int d[50011]; //first=cost,second=dest
vector< pair<int,int> > a[50011]; //first=dest,second=cost

void downheap(int p,int heapn){
	int l,r;
	while((p<<1)<=heapn){
		minim=p;
		l=p<<1;
		r=l+1;
		if(mymin[d[minim]]>mymin[d[l]])
			 minim=l;
		if(r<=heapn&&mymin[d[minim]]>mymin[d[r]])
			 minim=r;
		if(minim!=p){
			 int t=d[p];
			 d[p]=d[minim];dest[d[minim]]=p;
			 d[minim]=t;dest[t]=minim;
			 p=minim;
		}
		else break;
	}
}

void upheap(int p){
	int t;
	int x=d[p];
	t=p>>1;
	while(p>1 && mymin[x]<mymin[d[t]]){
		    d[p]=d[t];
			dest[d[t]]=p;
			p=t;t=t>>1;		
		
	  	}
	d[p]=x;dest[x]=p;
}

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


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

d[++heapn]=1;

//rezolvare Nlog(N)
while (heapn){
    p=d[1];
		//stergem primul element si reactualizam heapul
	d[1]=d[heapn];
	dest[d[heapn]]=1;
	heapn--;
	downheap(1,heapn);
	//salvam costul minim pentru nodul eliminat
	               
 //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
	  where=a[p][i].first;
      cat=a[p][i].second;
	  if(mymin[p] + cat< mymin[where] ){
		  //daca vecinul exista in heap
		     mymin[where]=mymin[p]+cat;
		  //daca nu, il adaugam
		if(dest[where]==0){
			heapn++;
			d[heapn]=where;
            upheap(heapn);
		}
		else
			//daca vecinul exista in heap
			upheap(dest[where]);
	  }
}
}


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