#include<cstdio>
#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;
std::vector<int> v;
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;
     temp=A[1];
	 int cur=1;
	 while(!v.empty())
	 {
	    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;
	   v.erase(v.begin());
	   cur=q.top().first;
	   for(int i=0;i<q.size();i++)
		   q.pop();
	   temp=A[cur];
	 }
    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=1;i<N;i++)
		v.push_back(i);
	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;
}