#include<cstdio>
#include<vector>
#include<queue>
struct Node
{
	int value;
	int length;
	Node *node;
};

Node *A[50000];

int B[50000];
int check[50000];
class CompareDist
{
public:
    bool operator()(std::pair<int,int> n1,std::pair<int,int> n2)
    {

      if(n1.second>n2.second)
      return true;
      else
      return false;

    }
};
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,CompareDist> q;
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;
}
void dijkstra(int N)
{
   Node *temp;
     temp=A[1];
	 int t=N;
	 int cur=1;
	 int min=(1<<30);
	 while(t)
	 {
	    while(temp)
	    {
		 if(check[temp->value]==0 && (B[cur] + temp->length) < B[temp->value])
		 {
             B[temp->value]=B[cur] + temp->length;
			 q.push(std::make_pair(temp->value,B[temp->value]));
		 }
		 temp=temp->node;
	   }
	   check[cur]=1;
	   --t;
	   if(!q.empty())
	     cur=q.top().first;
	   else
		   for(int i=1;i<=N;i++)
			   if(check[i]==0 && i!=cur)
			   {
				   if(B[i]<min)
				   {
					   min=B[i];
					   cur=i;
				   }
			   }
      for(int i=1;i<=q.size();i++)
		  q.pop();	
	  min=(1<<30);
	   temp=A[cur];
	 }
}
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(N);
   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;
}