#include<stdio.h>

#define max 50002
#define inf 1<<30

int n,m,k;

int heap[max],nodes[max],pos[max],l,hl;
bool visited[max];
struct node
{
	int dest,cost;
	node* next;
} *roads[250005];


void push(int x,int y,int z)
{
	node *p=new node;
	p->dest=y;
	p->cost=z;
	p->next=roads[x];
	roads[x]=p;
}
void swap(int x, int y)
{
    int t = heap[x];
    heap[x] = heap[y];
    heap[y] = t;
}
 
void upheap(int who)
{
      int aux;
	  while(who/2 && nodes[heap[who]]<nodes[heap[who/2]] )
	  {
		  aux=heap[who];
		  heap[who]=heap[who/2];
		  heap[who/2]=aux;

		  pos[heap[who]]=who/2;
		  pos[heap[who/2]]=who;
		  who/=2;
	  }
}
void downheap()
{
	int loc=1,x=0;
	int aux;

	while(x!=loc && loc<=k && x<=k)
	{
		x=loc;
		 if( 2*x<=n && nodes[heap[2*x]]<nodes[heap[x]] ) x=x*2;
		 if( 2*x+1<=n && nodes[heap[2*x+1]]<nodes[heap[x]]) x=x*2+1;
		 if(x<=k)
		 {
		  aux=heap[loc];
		  heap[loc]=heap[x];
		  heap[x]=aux;

		  pos[heap[loc]]=x;
		  pos[heap[x]]=loc;
		 }
		  loc=x;
	}
}

void dijkstra()
{
	for(int i=2;i<=n;i++)
		nodes[i]=inf,pos[i]=-1;
	pos[1]=1;
	heap[++k]=1;

	while(k)
	{
		int min=heap[1];
		swap(1,k);
		pos[heap[1]]=1;
		--k;

		downheap();

		node *q=roads[min];

		while(q)
		{
			if(nodes[q->dest] > nodes[min] + q->cost)
			{
				nodes[q->dest]=nodes[min] + q->cost;

                if(pos[q->dest] !=-1)
					upheap(pos[q->dest]);
				else
				{
					heap[++k]=q->dest;
					pos[heap[k]]=k;
					upheap(k);
				}
			}
			q=q->next;
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	scanf("%d%d",&n,&m);
	hl=1;
	int x,y,z;

	for(int i=1;i<=m;i++) 
	{
		scanf("%d%d%d",&x,&y,&z);
		push(x,y,z);
	}

    
   dijkstra();

	for(int i=2;i<=n;i++)
	  if(nodes[i] != inf)
		printf("%d ",nodes[i]);
	  else
		  printf("0 ");
	return 0;
}