#include<fstream.h>
#define inf 100000000
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct arc{unsigned short a,b,c;};

struct nod{int nr,w;nod *adr;};
struct lista{nod *vf,*sf;};

lista l[50001];
int n,m,d[50001],c[50001],ls,li;
arc v[250001];

void init(){
	li=1;
	ls=0;
}

int coadavida(){
	return li>ls;
}

void pune(int x){
	ls++;
	c[ls]=x;
}

void scoate(int &x){
	x=c[li];
	li++;
}

void add(lista &l,int x,int c){
	nod *nn=new nod;
	nn->nr=x;
	nn->w=c;
	nn->adr=NULL;
	if(!l.vf) l.vf=nn;
	else l.sf->adr=nn;
	l.sf=nn;
}

	

void B_F(){
	int x,y,z;
	nod *nc;
	pune(1);
	while(!coadavida()){
		scoate(x);
		nc=l[x].vf;
		while(nc){
			y=nc->nr;
			z=nc->w;
			if(d[x]+z<d[y]) d[y]=d[x]+z;
			pune(y);
			nc=nc->adr;
		}
	}
}
int main(){
	int i;
	fin>>n>>m;
	for(i=2;i<=n;i++) d[i]=inf;
	for(i=1;i<=m;i++) fin>>v[i].a>>v[i].b>>v[i].c;
	for(i=1;i<=m;i++) {
		add(l[v[i].a],v[i].b,v[i].c);
		if(v[i].a==1) d[v[i].b]=v[i].c;
	}
	B_F();
	for(i=2;i<=n;i++) fout<<d[i]<<" ";
	return 0 ;
}