#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 50010

typedef vector< pair<int,int> > vii;

vii G[MAX];
int D[MAX], Visits[MAX];
int N, M;
bool enq[MAX], cycle;

queue<int> Q;


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

	scanf("%d %d", &N, &M);
	while ( M-- )
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		G[x].push_back(make_pair(y,c));
	}

	memset(D, 0x3f, sizeof(D));
	D[1] = 0;
	Q.push(1);
	enq[1] = true;
	cycle = false;
	while ( Q.size() >= 1 && !cycle )
	{
		int x = Q.front(); Q.pop();
		enq[x] = false;
		Visits[x] ++;
		if ( Visits[x] > N )
		{
			cycle = true;
			break;
		}
		for (vii::iterator i=G[x].begin(); i!=G[x].end(); ++i)
		{
			if ( D[x] + i->second < D[i->first] )
			{
				D[i->first] = D[x] + i->second;
				if ( !enq[i->first] )
				{
					Q.push(i->first);
					enq[i->first] = true;
				}
			}
		}
	}

	if ( cycle )
	{
		printf("Ciclu negativ!");
	}
	else
	{
		for (int i=2; i<=N; ++i)
			printf("%d ", D[i]);
		printf("\n");
	}
	return 0;
}