# include <algorithm>
# include <queue>
# include <vector>
# define nmax 50005
# define INF 2000000005

using namespace std;

int n,m,d[nmax],viz[nmax],ap[nmax],x,y,c,k;
vector <pair <int,int> > G[nmax];
queue <int> Q;

void bf()
{
	int x;
	vector <pair <int,int> >::iterator it;
	
	fill(d+1,d+n+1,INF);
	d[1]=0;
	ap[1]=1;
	Q.push(1);
	while (!Q.empty())
	{
		x=Q.front();
		viz[x]=0;
		for (it=G[x].begin();it!=G[x].end();++it)
			if (d[it->first]>d[x]+it->second)
			{
				d[it->first]=d[x]+it->second;
				if (!viz[it->first])
				{	
					viz[it->first]=1;
					Q.push(it->first);
					if (++ap[it->first]==n)
					{
						k=1;
						return;
					}
				}
			}
		Q.pop();
	}
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d", &n, &m);
	for (; m; --m)
	{
		scanf("%d %d %d", &x, &y, &c);
		G[x].push_back(make_pair(y,c));
	}
	bf();
	if (k)
		printf("Ciclu negativ!");
	else
		for (int i=2;i<=n;i++)
			printf("%d ", d[i]);
	return 0;
}