#include<fstream>
#include<list>
#include<queue>
#define NMAX 50005
#define MMAX 250000
#define INF 250000000

using namespace std;

struct muchie 
{
	int y, c, nr;
};

int d[NMAX], vz[MMAX], n, m, i;
list<muchie>:: iterator it;
list<muchie> a[NMAX];
queue<int> q;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

void citeste()
{
	int i, x, y, c;
	muchie r;
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y>>c;
		r.y=y;r.c=c;r.nr=i;
		a[x].push_back(r);
	}
	for (i=2; i<=n; ++i) d[i]=INF;
}

void bellmanford()
{
	int i, x, sum, ok=1;
	muchie r;
	q.push(1);
	while (!q.empty() && ok)
	{	
		x=q.front();q.pop();
		for (it=a[x].begin(); it!=a[x].end(); ++it)
		{
			r=*it;
			sum=d[x]+r.c;
			if (d[r.y]>sum)
			{
				d[r.y]=sum;
				q.push(r.y);
				++vz[r.nr];
				if (vz[r.nr]>n-1) 
					{
						ok=0;
						break;
					}
			}
		}
	}
	if (ok) for (i=2; i<=n; ++i) g<<d[i]<<" ";
		else g<<"Ciclu negativ!";
}
	

int main()
{
	citeste();
	bellmanford();
	f.close();
	g.close();
	return 0;
}