#include<iostream>
#include<fstream>
#include<queue>

using namespace std;

#define MAX 50010

int N,M;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct Node
{
	int i,c;
	Node * next;
}*A[MAX];
int viz[MAX],B[MAX];
void add_to_list(int k,int i,int c)
{
	Node *q=new Node;
	q->i=i;
	q->c=c;
	q->next=A[k];
	A[k]=q;
}


class Compare
{
public:
	bool operator ()(Node n1,Node n2)
	{
		return n1.c>n2.c;
	}
};

priority_queue<Node,vector<Node>,Compare> q;

void dijkstra()
{
	Node temp,el;
	B[1]=0;
	viz[1]=0;
	temp.i=1;
	temp.c=B[1];
	q.push(temp);
	Node *p;
	 for(int i=2;i<=N;i++)
	 {
		  B[i]=(1<<30);
	 }
	while(!q.empty())
	{
		el=q.top();
		q.pop();
		p=A[el.i];
			while(p)
			{
				if(!viz[p->i])
				{
					 if(p->c + B[el.i] <B[p->i])
					{
					   B[p->i]=p->c + B[el.i];
					   temp.i=p->i;
					   temp.c=B[p->i];
					   q.push(temp);
					}
				}
				p=p->next;
			}
	   viz[el.i]=1;
	}
}

int main()
{
   in>>N>>M;
   int k,j,c;
   for(int i=1;i<=M;i++)
   {
	   in>>k>>j>>c;
	   add_to_list(k,j,c);
   }

   dijkstra();

   for(int i=2;i<=N;i++)
	   if(B[i]!=(1<<30))
	    out<<B[i]<<" ";
	   else
		out<<0<<" ";
 
   in.close();
   out.close();
	return 0;
}