#include<stdio.h>
typedef struct vecter
{
	long info;
	long dist;
	vecter *next;
}*pvecter;   
pvecter L[50002],pp;   
long int n,m,i,a,b,c,i8,heaplenght,currentvecter,currentdistance,aux;
long int heap[50002],pozheap[50002],distance[50002],vizited[50002];
void add(pvecter &p,long j,long c)
{   
    vecter *q=new vecter;   
    q->info=b;   
    q->dist=c;   
    q->next=p;
	p=q;
}
void heapdown(long int parent)   
{   
    long int rightson,leftson;   
    leftson=parent<<1;
	rightson=leftson|1;   
    if(leftson>heaplenght)
		return;   
    if(leftson<heaplenght)
		if(distance[heap[rightson]]<distance[heap[leftson]])
			leftson=rightson;   
    if(distance[heap[leftson]]<distance[heap[parent]])
	{
		aux=heap[leftson];
		heap[leftson]=heap[parent];
		heap[parent]=aux;   
		pozheap[heap[leftson]]=leftson;
		pozheap[heap[parent]]=parent; 
		heapdown(leftson);
	}   
}
void heapup(long int parent)
{   
    long int leftson;   
    leftson=parent>>1;   
    if(!leftson)
		return;   
    if(distance[heap[leftson]]>distance[heap[parent]])
	{
		aux=heap[leftson];
		heap[leftson]=heap[parent];
		heap[parent]=aux;   
		pozheap[heap[leftson]]=leftson;
		pozheap[heap[parent]]=parent; 
		heapup(leftson);
	}   
}
int main()   
{   
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld %ld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&a,&b,&c);
		add(L[a],b,c);
	}
    i8=1000000000;   
    for(i=1;i<=n;i++)
	{
		heap[i]=i;
		pozheap[i]=i;
		distance[i]=i8;
	}
	distance[1]=0;
	heaplenght=n;   
    while(heaplenght && distance[heap[1]]<i8)
	{
		currentvecter=heap[1];
		vizited[currentvecter]=1;
		currentdistance=distance[currentvecter];
		heap[1]=heap[heaplenght];
		pozheap[heap[1]]=1;
		heaplenght--;
		heapdown(1);
		pp=L[currentvecter];
		while(pp)
		{
			if(vizited[pp->info])
				pp=pp->next;
			else
			{
				if(distance[pp->info]>currentdistance+pp->dist)
				{
					distance[pp->info]=currentdistance+pp->dist;
					heapup(pozheap[pp->info]);
				}
				pp=pp->next;
			}
		}
	}
	for(i=2;i<=n;i++)
	{
		if(distance[i]==i8)
			distance[i]=0;
		printf("%ld ",distance[i]);
	}   
    printf("\n");
	return 0;   
}