#include<fstream>
#include<queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,cost[50005],pas,a,b,c,w,y;
struct nod
{ int nr;
  int c;
  nod *urm;
} *v[50005],*p;
queue<int> q;
char prez[50005];
int main()
{
	int i;
	f>>n>>m;
	for(i=0;i<m;++i)
		{ f>>a>>b>>c;
		  p=new nod;
		  p->nr=b;
		  p->c=c;
		  p->urm=v[a];
		  v[a]=p;
		}
	for(i=2;i<=n;i++) cost[i]=INT_MAX;
	q.push(1);
	pas=1;
	y=n*n;
	while(!q.empty()&&pas<y)
		{ ++pas;
		  w=q.front();
		  q.pop();
		  prez[w]='\0';
		  p=v[w];
		  while(p)
			  { if(cost[p->nr]>cost[w]+p->c)
				  { cost[p->nr]=cost[w]+p->c;
				    if(!prez[p->nr]) q.push(p->nr),prez[p->nr]='1';
				  }
				p=p->urm;
			  }
		}
	if(q.empty()) for(i=2;i<=n;i++) g<<cost[i]<<' ';
		else g<<"Ciclu negativ!";
	g<<'\n';
	f.close(); g.close();
	return 0;
}