#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
using namespace std;
#define inf 0xffffff
#define Max 50001

vector<pair<int,int> >g[Max];
queue<int>s1,s2;
int n,d[Max];

void bellman()
{
	int x,y;
	for(int i=2;i<=n;i++)d[i]=inf;
	s1.push(1);
	for(int i=1;i<=n;i++)
	{
		while(s1.size()>0)
		{
		x=s1.front();
		s1.pop();
		for(int i=0;i<g[x].size();i++)
		{
			y=g[x][i].first;
			if(d[y]>d[x]+g[x][i].second)
			{
				d[y]=d[x]+g[x][i].second;
				s2.push(y);
			}
		}
		}
		swap(s1,s2);
	}
	if(s1.size()>0)printf("Ciclu Negativ!"); else
	{
		for(int i=2;i<=n;i++)printf("%d ",d[i]);
	}
}

int main()
{
	int m,x,y,c;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
		scanf("%d %d",&n,&m);
		while(m--)
		{
			scanf("%d %d %d",&x,&y,&c);
			g[x].push_back(make_pair(y,c));
		}
		bellman();
	return 0;
}