#include<fstream>
#include<vector>
#include<queue>
#include<stdio.h>
using namespace std;

#define inf INT_MAX

struct nod{int nr, val;};
vector<nod> v[50002];
queue<int>q;
int N,M,d[50002],X=1,p[50002],viz[50002];

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 af()
{
	ofstream out("bellmanford.out");
	out<<"Ciclu negativ!\n";
	out.close();
	exit (0);
}
	

void bf()
{
	int i,y;
	for(i=2;i<=N;i++)
		d[i]=inf;		
	//for(int i=1;i<=N;i++)
	q.push(1);
	p[1]=0;	 
	i=q.front();
	while(!q.empty())
	{
		i=q.front();
		q.pop();
		for(int j=0;j<(int)v[i].size();j++)
		{
			y=v[i][j].nr;
			viz[y]++;
			if(d[i]+v[i][j].val<d[y])
			{
				d[y]=d[i]+v[i][j].val;
				p[y]=i;
				q.push(v[i][j].nr);				
			}			
		}
		if ((int)q.size()>N+3)
			af();
		for(i=1;i<=N;i++)
			if(viz[i]>=(N-1))
				af();
	}	
}

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