#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define inf INT_MAX

struct nod{int nr, val;};
vector<nod> v[50000];
queue<int>q;
int N,M,d[50000],X,Y,p[50000];

void citire()
{
	nod p;
	ifstream in("bellmanford.in");
	in>>N>>M;
	
	for(int i=1;i<=N;i++)
		{	
			p.nr=i;
			p.val=0;
			v[i].push_back(p);
			
		}
	int j,k,x;
	while(in>>j>>k>>x)
	{
		p.nr=k;
		p.val=x;
		v[j].push_back(p);
		/*p.nr=j;
		p.val=x;
		v[k].push_back(p);*/
	}
	in.close();
}


void bf()
{
	for(int i=1;i<=N;i++)
		if(i==X)
			d[i]=0;
		else
			d[i]=inf;
		
	//for(int i=1;i<=N;i++)
		q.push(X);
		p[X]=0;
		int i; 
		i=q.front();
	while(!q.empty())
	{
		i=q.front();
		for(int j=0;j<v[i].size();j++)
		{
			if(d[i]+v[i][j].val<d[v[i][j].nr])
			{
				d[v[i][j].nr]=d[i]+v[i][j].val;
				p[v[i][j].nr]=i;
				q.push(v[i][j].nr);
				
			}
				
			
		}
	q.pop();
	}
	
}
int main()
{
	citire();
	
	bf();
	ofstream out("bellmanford.out");
	//for(int i=0;i<=N;i++)
	///	{for(int j=1;j<v[i].size();j++)

	//		out<<v[i][j].nr<<" "<<v[i][j].val<<" ";
	//	out<<endl;}
	for(int i=2;i<=N;i++)
		out<<d[i]<<" ";
	out<<'\n';
}