#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];
int dest[50001];
int mymin[50001];
pair<int,int> d[50001]; //first=cost,second=dest
vector< pair<int,int> > a[50001];

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

void upheap(int p){
	int t;
	while(p>1){
		t=p/2;
		if(d[p]<d[t]){
			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(){
	fscanf(f,"%d%d",&n,&m);

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

//d[i]= distanta de la nod1 la nodi
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 N2
for(k=2;k<=n;k++){
	//cel mai apropiat nod la care se poate ajunge
    p=d[1].second;
	int cost=d[1].first;
	d[1]=d[heapn];
	heapn--;
	downheap(1);
	dest[d[1].second]=1;
	  if(mymin[p]>cost)
		  mymin[p]=cost;
                   
 //selectam nodul
 s[p]=1;
 //minimul pana la toti vecinii
  for(i=0;i<=(int)a[p].size()-1;i++)
	  if(s[a[p][i].first]==0 && cost +a[p][i].second < d[dest[a[p][i].first]].first )
		  if(dest[a[p][i].first]!=0)
	     d[dest[a[p][i].first]].first=cost+a[p][i].second;
		  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);
		  }			   
}
//afisam
for(i=2;i<=n;i++){
	if(mymin[i]!=inf)
	fprintf(g,"%d ",mymin[i]);
	else fprintf(g,"%d ",0);
}
return 0;
}