#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define f first
#define s second
#define NMAX 50000
#define inf 2000000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, nr[NMAX+10], cost[NMAX+10];
bool viz[NMAX+10];
vector <pair <int, int> > nod[NMAX+10];
queue <int> Q;

int main()
{
	fin >> n >> m;
	for(int i=1; i<=m; i++)
		{	int nod1, nod2, cost;
			fin >> nod1 >> nod2 >> cost;
			nod[nod1].push_back({cost, nod2});
		}
	for(int i=2; i<=n; i++)
		cost[i] = inf;
	Q.push(1);
	while(!Q.empty())
		{	int a = Q.front();
			Q.pop();
			viz[a] = 0;
			for(auto u : nod[a])
				{	int d = cost[a] + u.f;
					if(d < cost[u.s])
						{	cost[u.s] = d;
							if(!viz[u.s])
								{	Q.push(u.s);
									nr[u.s]++;
									if(nr[u.s] >= n)
										{	fout << "Ciclu negativ!" << '\n';
											cout << u.s << '\n';
											return 0;
										}
								}
						}
				}
		}
	for(int i=2; i<=n; i++)
		fout << cost[i] << ' ';
	fout << '\n';
	return 0;
}