#include<stdio.h>
#define Nmax 50010
#define Inf 1<<30

int n,m,h[Nmax],poz[Nmax],best[Nmax],i,cst,x,y,k;
struct graf {int inf,cost; graf *adr;} *v[Nmax];


void add(int i, int j, int cst)
{
	graf *c;
	c=new graf;
	
	c->inf=j;
	c->cost=cst;
	c->adr=v[i];
	v[i]=c;
}

void swap(int i, int j)
{
	int aux;
	aux=poz[h[i]]; poz[h[i]]=poz[h[j]]; poz[h[j]]=aux;
	aux=h[i]; h[i]=h[j]; h[j]=aux;
	
}

int pozmin(int i)
{
	if(2*i+1<=k)
		
		if( best[ h[2*i+1] ] < best[ h[2*i] ] ) return 2*i+1;
	
	return 2*i;
}


void down(int i)
{
	int p;
	
	if(i<=k/2)
	{
		p=pozmin(i);
		
		if(best[h[i]] > best[h[p]]) 
		{
			swap(i,p);
			down(p);
		}
	}
}

void up(int i)
{
	if(i>1)
	{
		if(best[h[i]]>best[h[i>>1]])
		{
			swap(i,i>>1);
			up(i>>1);
		}
	}
}

void dijkstra()
{
	int i;	
	for(i=2;i<=n;i++)
	{
		best[i]=Inf;
		poz[i]=-1;
	}
	poz[1]=1; 
	h[++k]=1;
	
	while(k)
	{
		int nod=h[1];
		swap(1,k);
		k--;
		down(1);
		
		graf *c;
		c=new graf;
		
		for(c=v[nod];c;c=c->adr)
		{
			if( best[c->inf] > best[nod] + c->cost)
			{
				best[c->inf]=best[nod]+c->cost;
				
				if(poz[c->inf]==-1) { h[++k]=c->inf; poz[c->inf]=k; up(k);}
				else up(poz[c->inf]);
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&cst);
		
		add(x,y,cst);
	}
	
	dijkstra();
	
	for(i=2;i<=n;i++)
	{
		if(best[i]==Inf) printf("0 ");
		else printf("%d ",best[i]);
	}
	
	return 0;
}