#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
#define mp make_pair
#define Nmax 50001
#define INF 1000000
using namespace std;
vector< pair<int, int> > G[Nmax];
queue <int> q;
int N, M, i, d[Nmax], ap[Nmax];
int BellmanFord()
{
	int x;
	d[1]=0; q.push(1);
	ap[1]=1;
	for(i=2;i<=N;++i)
		d[i]=INF;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=0;i<G[x].size();i++)
			if(d[x]+G[x][i].second<d[G[x][i].first])
			{
				d[G[x][i].first]=d[x]+G[x][i].second;
				q.push(G[x][i].first);
				ap[G[x][i].first]++;
				if(ap[G[x][i].first]>N)
				{
					printf("Ciclu negativ\n");
					return 0;
				}
			}
	}
	for(i=2;i<=N;++i)
		printf("%d ", d[i]);
	printf("\n");
}

int main()
{
	int a, b, c;
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for(i=1;i<=M;++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		G[a].pb(mp(b, c));
	}
	BellmanFord();
	fclose(stdin);
	fclose(stdout);
	return 0;
}