#include<stdio.h>

#define max 50002
#define inf 10000;

int n,m;

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 edit(int who,int iasdfdas)
{
      int aux;
	  if(!who)
	  {
		  heap[++l]=iasdfdas;
		  pos[iasdfdas]=l;
		  who=l;
	  }
	  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 kill()
{
	pos[heap[1]]=-1;
	pos[heap[l]]=1;
	heap[1]=heap[l--];
	
	int loc=1,x=0;
	int aux;

	while(x!=loc)
	{
		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;

		  aux=heap[loc];
		  heap[loc]=heap[x];
		  heap[x]=aux;

		  pos[heap[loc]]=x;
		  pos[heap[x]]=loc;
		  loc=x;
	}
}
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);
	}

    
	for(int i=0;i<=n;i++)
		nodes[i]=inf;
	
	nodes[1]=0;
	heap[1]=1;
	pos[1]=1;
	l=1;

	while(l)
	{
		node *p;
		for( p = roads[heap[1]] ; p != NULL ; p=p->next )
			if(!visited[p->dest])
				if( nodes[heap[1]]+p->cost < nodes[(p->dest)] )
				{
					 nodes[p->dest]=nodes[heap[1]]+p->cost;
					 edit(pos[p->dest],p->dest);
				}
		visited[heap[1]]=1;
	    kill();
	}

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