#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-1;
	 int cur=1;
	 int ok=0;
	 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;
	   cur=q.top().first;
      for(int i=1;i<=q.size();i++)
		  q.pop();			 
	   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(5);
   for(int i=2;i<=N;i++)
	 fprintf(file_out,"%d ",B[i]);

	fclose(file_in);
	fclose(file_out);

}

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