#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 <pair <int, 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({0, 1});
	while(!Q.empty())
		{	pair <int, int> a = Q.front();
			Q.pop();
			viz[a.s] = 0;
			nr[a.s]++;
			if(nr[a.s] == n)
				{	fout << "Ciclu negativ!" << '\n';
					return 0;
				}
			for(auto u : nod[a.s])
				{	int d = a.f + u.f;
					if(d < cost[u.s])
						{	cost[u.s] = d;
							if(!viz[u.s])
								Q.push({d, u.s});
						}
				}
		}
	for(int i=2; i<=n; i++)
		fout << cost[i] << ' ';
	fout << '\n';
	return 0;
}