#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 *p;
	while(!q.empty())
	{
		el=q.top();
		p=A[el];
		q.pop();
		if(!viz[el])
		{
			viz[el]=1;
			while(p)
			{
				if(!viz[p->i])
				{
					if(p->c + B[el] <B[p->i])
					{
					   B[p->i]=p->c + B[el];
					   q.push(p->i);
					}
				}
				p=p->next;
			}
		}
	}
}

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;
}