#include<cstdio>
#include<vector>
#define MULT 2000000
using std::vector;

struct edge
{
	int i,j,c;
	edge ()
		{
			i=j=c=0;
		}
	edge (int ii, int jj, int cc)
		{
			i=ii;
			j=jj;
			c=cc;
		}
};
vector<edge> v;
int d[50005];

int main()
{
	freopen ("bellmanford.in","r",stdin);
	freopen ("bellmanford.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);

	while(m--){
		int x,y,c;
		scanf ("%d%d%d",&x,&y,&c);
		v.push_back (edge (x-1,y-1,c));
	}

	for(int i=1;i<n;i++)
		d[i]=MULT;

	for(int i=0;i<n;i++)
		for(vector<edge>::iterator it=v.begin();it!=v.end();it++){
			int i=it->i;
			int j=it->j;
			int c=it->c;
			if(d[i]+c<d[j]){
				if(i==n){
					puts ("Ciclu negativ!");
					return 0;
				}
				else
					d[j]=d[i]+c;
			}
		}
	for(int i=1;i<n;i++)
		printf ("%d ",d[i]);
	return 0;
}