#include<vector>
#include<bitset>
#include<fstream>
#include<queue>
#include<algorithm>
#define maxn 50005
#define inf 1<<30

using namespace std;
bool ciclu;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
queue <int> Q;
vector<pair <int,int> > A[maxn];
bitset<maxn> uz;
int d[maxn];
int cnt[maxn];

void read()
{
	in>>n>>m;
	int a,b,c;
	for(int i=1;i<=m;i++)
	{
		in>>a>>b>>c;
		A[a].push_back( make_pair(b,c));
	}
	for(int i=1;i<=n;i++) d[i]=inf;
}

void solve()
{
	Q.push(1);
	d[1]=0;
	int nod;
	while(!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		uz[nod]=false;
		vector < pair <int, int> >::iterator it;
		for(it=A[nod].begin();it!=A[nod].end();it++)
		{
			if(d[it->first]>it->second+d[nod])
			{
				d[it->first]=it->second+d[nod];
			if(uz[it->first]==false)
			{
			if(cnt[it->first]>n) ciclu=true;
			else
			{
				
				Q.push(it->first);
				cnt[it->first]+=1;
				
			}
			}
			}
		}
	}
}
			
		
int main()
{
	ciclu=false;
	read();
	solve();
	if(ciclu==true) out<<"Ciclu negativ!";
	else 
		for(int i=2;i<=n;i++)
			out<<d[i]<<" ";
}