#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50005
#define INF (1<<30)
#define US unsigned short
using namespace std;
vector <pair<US,short> > G[NMAX];
queue<int> Q;
int d[NMAX],n;
US nr[NMAX];
bool use[NMAX];
void read()
{
	ifstream fin("bellmanford.in");
	int m;
	US x,y;
	short c;
	fin>>n>>m;
	for(int i=0;i<m;i++)
	{
		fin>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	fin.close();
}
bool bellmanford(US nod)
{
	for(US i=1;i<=n;i++)
		d[i]=INF;
	US vec;
	short cost;
	Q.push(nod);
	d[nod]=0;
	while(!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		if(nr[nod]>=2)
			return 0;
		use[nod]=1;
		nr[nod]++;
		for(size_t i=0;i<G[nod].size();i++)
		{
			vec=G[nod][i].first;
			cost=G[nod][i].second;
			if(d[vec]>d[nod]+cost)
			{
				if(use[vec])
					continue;
				d[vec]=d[nod]+cost;
				Q.push(vec);
			}
		}
	}
	return 1;
}
void solve(US nod)
{
	ofstream fout("bellmanford.out");
	if(bellmanford(nod))
		for(int i=2;i<=n;i++)
			fout<<d[i]<<' ';
	else
		fout<<"Ciclu negativ!";
	fout.close();
}
int main()
{
	read();
	solve(1);
	return 0;
}