using namespace std;
#include<cstdio>
#define nmax 50001
#define inf 3000
struct nod { int v,c; nod * next;};
nod* a[nmax];
int h[nmax], poz[nmax], use[nmax],n,m,d[nmax],nr,k;

void swap (int x, int y)
{
	int aux=h[x];
	h[x]=h[y];
	h[y]=aux;
	poz[h[x]]=x;
	poz[h[y]]=y;
}

void downheap(int x)
{
	int fiu=2*x;
	while(fiu<=nr)
	{
		if(fiu<nr && d[h[fiu]]>d[h[fiu+1]]) fiu++;
		if(d[h[fiu]]<d[h[x]])
		{
			swap(x,fiu);
			x=fiu;
			fiu=fiu*2;
		}
		else fiu=nr+1;
	}
}

void upheap(int x)
{
	int tata=x/2;
	while(tata && d[h[tata]]>d[h[x]])
	{
		swap(tata,x);
		x=tata;
		tata=tata/2;
	}
}


void add(int x, int y,int z)
{
	nod*p=new nod;
	p->v=y;
	p->c=z;
	p->next=a[x];
	a[x]=p;
}

int main()
{
	int i,x,z,y;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	for(i=1;i<=n;i++) {d[i]=inf; poz[i]=-1;}
	for(nod *u=a[1];u;u=u->next)
		{
			d[u->v]=u->c;
			h[++nr]=u->v;
			poz[u->v]=nr;
			upheap(nr);
		}
	use[1]=1;
	k=1;
	while(k<n)
	{
		x=h[1];
		swap(1,nr);
		nr--;
		use[x]=1;
		k++;
		for(nod *u=a[x];u;u=u->next)
			if(!use[u->v])
				if(d[u->v]>d[x]+u->c)
				{
					d[u->v]=d[x]+u->c;
					if(poz[u->v]==-1) 
					{
						h[++nr]=u->v;
						poz[u->v]=nr;
						upheap(nr);
					}
					else upheap(poz[u->v]);
				}
	}
	for(i=2;i<=n;i++)
		if(d[i]==inf) printf("0 ");
		else printf("%d ",d[i]);
	return 0;
}