#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#define max 50005
using namespace std;
vector<pair<int,int> >g[max];

int d[max],n,m,prim,qnodes[max];
const int pinf = 0x3f3f3f3f;

void citire()
{int x,y,c;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
	{scanf("%d %d %d",&x,&y,&c);
	g[x].push_back(make_pair(y,c));}}

void solve()
{bool viz[max];
int negative=0;
queue<int>c;
fill(&d[0],&d[n+1],pinf);
fill(&viz[0],&viz[n+1],0);

d[prim]=0;
c.push(prim);
viz[prim]=1;

while(!c.empty()&&!negative)
{int nod=c.front();
c.pop();
viz[nod]=0;
for(vector<pair<int,int> >::iterator it=g[nod].begin();it!=g[nod].end();++it)
	if(d[nod]<pinf)
	if(d[nod] + it->second < d[it->first]) 
	{d[it->first]=it->second+d[nod];
	if(viz[it->first]==0)
	{
	if(qnodes[it->first]>n)
		negative=1;
	else
	{
	viz[it->first]=1;
	c.push(it->first);
	qnodes[it->first]++;
	}
	}}
}
if(negative)
	printf("Ciclu negativ!\n");
else
for(int i=2;i<=n;i++)
if(d[i]<pinf)printf("%d ",d[i]);
else
printf("%d ",0);	

}


int main ()
{freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
prim=1;
citire();
solve();

return 0;
}