//http://infoarena.ro/problema/dijkstra
#include<stdio.h>
using namespace std;
int n,m,nh;

struct graf
{
	int v,c;
	graf *adr;
};

struct heap
{
	int c,v1,v2;
};

graf *v[50002];//graful
heap h[100002];//heap ordonat dupa cost
char viz[50002];
int d[50002];//dist de la vf 1 la toate celelalte

void citire()
{
	int i,x,y,c;
	graf *p;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&c);
		p=new graf;
		p->v=y;
		p->c=c;
		p->adr=v[x];
		v[x]=p;
	}
}

void swap(int x,int y)//interschimbam 2 valori din heap
{
	heap aux;
	aux=h[x];
	h[x]=h[y];
	h[y]=aux;
}

void heapjos(int k)//mutam o val cat mai jos in heap
{
	int x,fs,fd;
	do
	{
		x=0;
		fs=k*2;//fiul din stanga
		fd=k*2+1;//fiul din dreapta
		if(fs<=nh)
		{
			x=fs;
			if(fd<=nh && h[fd].c < h[fs].c)
				x=fd;
			if(h[x].c >= h[k].c)
				x=0;
		}
		if(x)
		{
			swap(x,k);
			k=x;
		}
	}while(x);
}

void heapsus(int k)//mutam o val cat mai sus in heap
{
	int t;
	t=k/2;
	while(k>1 && h[k].c < h[t].c)
	{
		swap(t,k);
		k=t;
		t=k/2;

	}
}

void dijkstra()
{
	int v1,v2;
	graf *p;
	for(p=v[1];p;p=p->adr)
	{
		++nh;
		h[nh].c=p->c;
		h[nh].v1=1;
		h[nh].v2=p->v;
		heapsus(nh);
	}
	viz[1]=1;
	while(nh!=0)
	{
		v1=h[1].v1;
		v2=h[1].v2;
		if(viz[v1]==1 && viz[v2]==0)
		{
			d[v2]=h[1].c;
			viz[v2]=1;
			for(p=v[v2];p;p=p->adr)
				if(viz[p->v]==0)
				{
					++nh;
					h[nh].v1=v2;
					h[nh].v2=p->v;
					h[nh].c=d[v2]+p->c;
					heapsus(nh);
				}
		}
		h[1]=h[nh];		
		--nh;
		heapjos(1);
	}
}

void scrie()
{
	int i;
	for(i=2;i<=n;++i)
		printf("%d ",d[i]);
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();	
	dijkstra();
	scrie();
	fclose(stdin);
	fclose(stdout);
	return 0;
}