//Ilie Dumitru
#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
const int NMAX=50005, MMAX=250005;
const int oo=0x3f3f3f3f;

FILE *f=fopen("bellmanford.in", "r");
FILE *g=fopen("bellmanford.out", "w");

struct muchie
{
	int b, w;
};

int N, M;
std::vector<int> G[NMAX];
muchie muchii[MMAX];
std::bitset<NMAX> in_q;
int cnt[NMAX], dist[NMAX];

bool BellmanFord()
{
	std::queue<int> q;
	int i, nod, relax;

	for(i=1;i<N;++i)
		dist[i]=oo;

	q.push(0);
	while(!q.empty())
	{
		nod=q.front();
		q.pop();
		in_q[nod]=0;
		for(i=0;i<(int)G[nod].size();++i)
		{
			if(dist[nod]+muchii[G[nod][i]].w<dist[relax=muchii[G[nod][i]].b])
			{
				dist[relax]=dist[nod]+muchii[G[nod][i]].w;
				if(!in_q[relax])
				{
					if(cnt[relax]>N)
						return 1;
					++cnt[relax];
					q.push(relax);
					in_q[relax]=1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	int i, a;
	fscanf(f, "%d%d", &N, &M);
	for(i=0;i<M;++i)
	{
		fscanf(f, "%d%d%d", &a, &muchii[i].b, &muchii[i].w);
		--muchii[i].b;
		G[a-1].push_back(i);
	}
	if(BellmanFord())
		fprintf(g, "Ciclu negativ!\n");
	else
	{
		for(i=1;i<N;++i)
			fprintf(g, "%d ", dist[i]);
		fprintf(g, "\n");
	}
	fclose(f);
	fclose(g);
	return 0;
}