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

#define NMAX 50005
#define oo (1<<30)
#define US unsigned short

using namespace std;

vector <pair<US,short> > G[NMAX];
int d[NMAX], n, nr[NMAX];
bool inqueue[NMAX];
queue<int> 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(int nod)
{
	for(US i = 1; i <= n; i++)
		d[i] = oo;
	int vec, cost;
	Q.push(nod);
	d[nod] = 0;
	while(!Q.empty())
	{
		nod = Q.front();
		Q.pop();
		inqueue[nod] = 0;
		if(nr[nod] > n)
			return 0;
		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)
			{
				d[vec] = d[nod] + cost;
				nr[vec]++;
				if(!inqueue[vec])
					Q.push(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;
}