//dijkstra cu heap bc

#include <stdio.h>
#define nmax 50001

struct nod {int inf,cost; nod *urm;} *g[nmax];
int n,m,heap[nmax],poz[nmax],z,sol[nmax];

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

void baga(int x, int y, int c)
{
	nod *q=new nod;
	q->inf=y;
	q->cost=c;
	q->urm=g[x];
	g[x]=q;
}

void heap_down(int x)
{
	int f;
	while(x<=z)
	{
		if(x*2<=z)
		{
			f=x;
			if(f+1<=z)
				if(heap[sol[f+1]]<heap[sol[f]])
					f++;
		}
		else
			return;
		if(sol[heap[f]]<sol[heap[x]])
		{
			poz[heap[f]]=x;
			poz[heap[x]]=f;
			swap(x,f);
			x=f;
		}
		else
			return;
	}
}

void heap_up(int x)
{
	int tata;
	while(x>1)
	{
		tata=x/2;
		if(sol[heap[tata]]>sol[heap[x]])
		{
			poz[heap[tata]]=x;
			poz[heap[x]]=tata;
			swap(x,tata);
			x=tata;
		}
		else
			x=1;
	}
}

void dijkstra()
{
	int i;
	for(i=2;i<=n;i++)
	{
		poz[i]=-1;
		sol[i]=nmax;
	}
	poz[1]=1;
	heap[++z]=1;
	while(z)
	{
		int min=heap[1];
		swap(1,z);
		poz[heap[1]]=1;
		z--;
		heap_down(1);
		for(nod *q=g[min];q;q=q->urm)
		{
			if(sol[q->inf]>sol[min]+q->cost)
			{
				sol[q->inf]=sol[min]+q->cost;
				if(poz[q->inf]!=-1)
					heap_up(poz[q->inf]);
				else
				{
					heap[++z]=q->inf;
					poz[heap[z]]=z;
					heap_up(z);
				}
			}
		}
	}
}

int main()
{
	int i;
	int x,y,c;
	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,&c);
		baga(x,y,c);
	}
    dijkstra();
	for(i=2;i<=n;i++)
	{
		if(sol[i]==nmax)
			printf("0 ");
		else
			printf("%d ",sol[i]);
	}
	return 0;
}