#include<cstdio>
#define nmax 50001
#include<vector>
using namespace std;

vector < vector < pair < int , int > > >  v(nmax);
int viz[nmax],dist[nmax],C[250100],ok1;
int N,M;

void read();
void solve();
void write();

int main()
{
	freopen ("bellmanford.in","r",stdin);
	freopen ("bellmanford.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}

void read()
{
	int i,x,y;
	pair < int , int  > z;
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%d%d%d",&x,&y,&z.second);
		z.first=y;
		v[x].push_back(z);


	}
}

void solve()
{
	vector < pair < int , int > > :: iterator it;
	int sf,in,x,c;
	C[1]=1;
	in=sf=1;
	viz[1]=1;
	while (in<=sf&&sf<=250100)
	{
		for (it=v[C[in]].begin();it!=v[C[in]].end();++it)
		{
			x=(*it).first;
			c=(*it).second;
			if (!dist[x]||dist[x]>dist[C[in]]+c)
			{
				dist[x]=dist[C[in]]+c;
				if (!viz[x])
				{
					++sf;
					C[sf]=x;
					viz[x]=1;
				}
			}
		}
		viz[C[in]]=0;
		++in;
	}
	if (sf>250050)
		ok1=1;
}

void write()
{
	int i;
	if (ok1)
		printf("Ciclu negativ!\n");
	else
		for (i=2;i<=N;++i)
			printf("%d ",dist[i]);
}