#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
  
const string file = "bellmanford";
  
const string infile = file + ".in";
const string outfile = file + ".out";

int N, M;
vector<vector<pair<int, int> > > G;
vector<int> dst;

bool bellman()
{
	dst.resize(N + 1, 0x3f3f3f3f);
	dst[1] = 0;
	vector<bool> inQ(N + 1);
	vector<int> qCount(N + 1);

	queue<int> q;
	q.push(1);
	inQ[1] = true;
	while(q.empty() == false)
	{
		int current = q.front();
		q.pop();
		inQ[current] = false;
		for(vector<pair<int, int> >::iterator itr = G[current].begin();
			itr != G[current].end();
			itr++)
		{
			if(dst[itr->first] > dst[current] + itr->second)
			{
				dst[itr->first] = dst[current] + itr->second;
				if(inQ[itr->first] == false)
				{
					q.push(itr->first);
					inQ[itr->first] = true;
					qCount[itr->first] ++;
					if(qCount[itr->first] == N)	return false;
				}
			}
		}


	}
	return true;

}

int main()
{
	fstream fin(infile.c_str(), ios::in);
	fin >> N >> M;

	G.resize( N + 1);

	for(int i = 0; i < M; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));

	}
	fin.close();

	fstream fout(outfile.c_str(), ios::out);

	if(bellman())
	{
		for(int i = 2; i <= N; i++)
		{

			fout << dst[i]<< " ";
		}
	
	}
	else 
	{
		fout << "Ciclu negativ!";
	}

	fout.close();
}