#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>

#define NMAX 50005
#define oo (1<<30)
#define PII pair<int,int>
#define US unsigned short

using namespace std;

vector <pair<US,short> > G[NMAX];
int d[NMAX],n;
US nr[NMAX];
bool use[NMAX];
priority_queue<PII, vector<PII>, greater<PII> > Q;

void read()
{
	ifstream fin("bellmanford.in");
	int m;
	US x,y;
	short c;
	fin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y,c));
	}
	fin.close();
}

bool bellmanford(US nod)
{
	for(US i = 1; i <= n; i++)
		d[i] = oo;
	US vec;
	short cost;
	Q.push(make_pair(0, nod));
	d[nod] = 0;
	while(!Q.empty())
	{
		nod = Q.top().second;
		cost = Q.top().first;
		Q.pop();
		if(use[nod])
			continue;
		use[nod] = 1;
		for(size_t i = 0; i < G[nod].size(); i++)
		{
			vec = G[nod][i].first;
			cost = G[nod][i].second;
			if(d[vec] > d[nod] + cost)
			{
				if(use[vec])
					return 0;
				d[vec] = d[nod] + cost;
				Q.push(make_pair(d[vec], vec));
			}
		}
	}
	return 1;
}

void solve(US nod)
{
	ofstream fout("bellmanford.out");
	if(bellmanford(nod))
		for(int i = 2; i <= n; i++)
			fout << d[i] << ' ';
	else
		fout << "Ciclu negativ!";
	fout.close();
}

int main()
{
	read();
	solve(1);
	return 0;
}