#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 ()(int n1,int n2)
	{
		return B[n1]>B[n2];
	}
};

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

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