#include<cstdio>

struct Node
{
	int value;
	int length;
	Node *node;
};

Node *A[50000];

int B[50000];
int check[50000];
void add_to_list(int node_i,int value,int length)
{
	Node *node=new Node;
	node->value=value;
	node->node=A[node_i];
	node->length=length;
	A[node_i]=node;
}
int dijkstra(int N)
{
   Node *temp;
   for(int i=1;i<N;i++)
   {
     temp=A[i];
	 while(temp)
	 {
		 if(check[temp->value]==0 && (B[i] + temp->length) < B[temp->value])
		 {
			 B[temp->value]=B[i] + temp->length;
		 }
		 temp=temp->node;
	 }
	 check[i]=1;
   }
    for(int i=1;i<=N;i++)
	   check[i]=0;
  if(B[N] != (1<<30))
   return B[N];
  else
	return 0;
}
void exec(const char* file_i,const char* file_o)
{
	FILE *file_in=fopen(file_i,"r");
	FILE *file_out=fopen(file_o,"w");

	int N,M;
	fscanf(file_in,"%d%d",&N,&M);

	for(int i=0;i<M;i++)
	{
		int node,value,length;
		fscanf(file_in,"%d%d%d",&node,&value,&length);
		add_to_list(node,value,length);
	}
	for(int i=2;i<=N;i++)
		B[i]=(1<<30);
	dijkstra(5);
   for(int i=2;i<=N;i++)
    if(B[i] != (1<<30))
	 fprintf(file_out,"%d ",B[i]);
	else
     fprintf(file_out,"%d ",0);

	fclose(file_in);
	fclose(file_out);

}

int main()
{
	exec("dijkstra.in","dijkstra.out");
	return 0;
}