#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 9000000
using namespace std;
queue<int>c;
vector< pair <int,int> > g[50001];
int d[50002],n,m,inq[50002],ciclu,cnt[50001],i;
void initial()
{for(int j=1;j<=n;j++)
	{d[j]=INF;
	inq[j]=0;
	}
	d[1]=0;
}

void relaxare(int u,int p,int w)
{if(d[p]>d[u]+w)
	{ d[p]=d[u]+w;
	  cnt[p]++;
	  if(cnt[p]>n-1)
		   ciclu=1;
	  c.push(p);
	}
}

int solve()
{ initial();
  c.push(1);
  inq[1]=1;
  while(!c.empty())
  { int a=c.front();
    c.pop();
	inq[a]=0;
	 for(vector< pair<int,int> >::iterator it=g[a].begin();it!=g[a].end();it++)
		{ relaxare(a,it->first,it->second);
          if(ciclu==1)
		     return 0;
		}
   }
  return 1;
}

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