#include <stdio.h>
const long NMAX=50001;
struct nod{
	nod *urm;
	int cost,nd;

} *p[NMAX],*aux,*auxx;

int dd[NMAX],n,m,x,y,c,s[NMAX],k,min,j,gasit,pinf=2147483647;
int dim_heap,poz[NMAX];

struct frunza{int cost,nod; } d[50001];

inline int parinte(int i) {return i/2;}
inline int stanga(int i) {return 2*i;}
inline int dreapta(int i) {return 2*i+1;}

void reconstituie_heap(int i){
     int minim,t;
     int st=stanga(i);
     int dr=dreapta(i);
     
     if (st<=dim_heap && d[i].cost>d[st].cost) {minim=st;}
     else minim=i;
     if (dr<=dim_heap && d[dr].cost<d[minim].cost) {minim=dr;}
     
     if (minim!=i) {
                    poz[d[i].nod]=minim;
                    poz[d[minim].nod]=i;
                    
                    t=d[i].cost, d[i].cost=d[minim].cost,d[minim].cost=t;
                    t=d[i].nod, d[i].nod=d[minim].nod, d[minim].nod=t;
                    
                    reconstituie_heap(minim);
                   }
     
     }

int extrage_min(){
	int pz=d[1].nod;min=d[1].cost;
	d[1].cost=d[dim_heap].cost;
	d[1].nod=d[dim_heap].nod;
	dim_heap--;
	reconstituie_heap(1);
	return pz;
	}


void insereaza_in_heap(frunza element ){
	 int i;
	 dim_heap++;i=dim_heap;

	 while(i>1 && element.cost<d[parinte(i)].cost) {poz[d[parinte(i)].nod]=i; d[i].cost=d[parinte(i)].cost; d[i].nod=d[parinte(i)].nod; i=parinte(i);}

	 d[i].cost=element.cost;
	 d[i].nod=element.nod;

	 poz[d[i].nod]=i;

	 }

void update_heap(frunza element){
	int i=poz[element.nod];


	while(i>1 && element.cost<d[parinte(i)].cost) {poz[d[parinte(i)].nod]=i; d[i].cost=d[parinte(i)].cost; d[i].nod=d[parinte(i)].nod; i=parinte(i); }

	d[i].cost=element.cost;
	d[i].nod=element.nod;

	poz[d[i].nod]=i;

	}

int main()
{   int pz,sursa,i;frunza auxx;
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	sursa=1;
	for(i=1;i<=n;i++) dd[i]=pinf;
	for(i=1;i<=m;i++){
		scanf("%ld%ld%ld",&x,&y,&c);
		aux=new nod;
		aux->urm=p[x];
		aux->nd=y,aux->cost=c;
		p[x]=aux;
		if (x==sursa) {dd[y]=c;auxx.cost=c,auxx.nod=y; insereaza_in_heap(auxx);}
	}

	s[sursa]=1;

	for(i=1;i<=n-1 && dim_heap!=0;i++){
        pz=extrage_min();
        
        s[pz]=1;
		for(aux=p[pz];aux!=NULL;aux=aux->urm)
		 if(!s[aux->nd])
		 {	if (dd[aux->nd]>dd[pz]+aux->cost){
                auxx.nod=aux->nd, auxx.cost=dd[pz]+aux->cost;
				if (dd[aux->nd]==pinf) insereaza_in_heap(auxx);
				else update_heap(auxx);
                dd[aux->nd]=dd[pz]+aux->cost;}
		 }
		 
		 
	}

	for(i=2;i<=n;i++)
	 if (dd[i]==pinf) printf("0 ");
	 else printf("%d ",dd[i]);


	return 0;
}