#include <cstdio>

#define MaxN 100010
#define inf 2500001

struct nod{
	int x;
	int co;
	nod *urm;}*L[MaxN];
	
int heap[MaxN],N,M,poz[MaxN],cost[MaxN],H;


void add(int a,int y,int c)
{
	nod *q=new nod;
	
	q->x=y;
	q->co=c;
	q->urm=L[a];
	L[a]=q;
}
	

void cit()
{
	int i,x,y,c;
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		add(x,y,c);
	}
}

void init()
{
	for(int i=1;i<=N;i++)
		poz[i]=-1,cost[i]=inf;
}

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

void urca_heap(int x)
{
	while(cost[heap[x]]<cost[heap[x/2]]&&x>1)
	{
		poz[heap[x]]=x/2;
		poz[heap[x/2]]=x;
		swap(x,x/2);
		x=x/2;
	}
}

void cobor_heap(int x)
{
	while((cost[heap[2*x]]<cost[heap[x]]&&2*x<=H) ||(cost[heap[2*x+1]]<cost[heap[x]]&&2*x+1<=H))
	{
		if(2*x+1<=H)
		{
			if(cost[heap[2*x]]<cost[heap[2*x+1]])
			{
				poz[heap[x]]=2*x;
				poz[heap[2*x]]=x;
				swap(x,2*x);
				x=2*x;
			}
			else
			{
				poz[heap[x]]=2*x+1;
				poz[heap[2*x+1]]=x;
				swap(x,2*x+1);
				x=2*x+1;
			}
		}
		else
		{
			poz[heap[x]]=2*x;
			poz[heap[2*x]]=x;
			swap(x,2*x);
			x=2*x;
		}
	}
}
	

void rez()
{
	int min;
	nod *aux;
	init();
	H=1;
	heap[1]=1;poz[1]=1;cost[1]=0;
	while(H)
	{
		min=heap[1];
		swap(1,H);
		poz[heap[1]]=1;
		H--;
		cobor_heap(1);
		aux=L[min];
		while(aux)
		{
			if(cost[aux->x]>cost[min]+aux->co)
			{
				cost[aux->x]=cost[min]+aux->co;
				if(poz[aux->x]!=-1)
					urca_heap(poz[aux->x]);
				else
				{
					heap[++H]=aux->x;
					poz[aux->x]=H;
					urca_heap(poz[aux->x]);
				}
			}
			aux=aux->urm;
		}
	}
}

void afis()
{
	int i;
	for(i=2;i<=N;i++)
		if(cost[i]==inf)
			printf("0 ");
		else
			printf("%d ",cost[i]);
	printf("\n");
}
		

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