#include <fstream>
#include <vector>
#include <queue>
using namespace std;

struct muchie{
	int to, cost;
};

vector< muchie > G[50000];
int d[50000];
bool viz[50000];

int main(){
	int n, m;

	ifstream fin ("bellmanford.in");
	fin >> n >> m;

	for (int i = 0; i < m; i++){
		int x, y, c;

		fin >> x >> y >> c;

		x--; y--;

		G[x].push_back({y, c});
	}
	fin.close();

	queue< int > Q;
	vector< int > cntInQueue(n, 0);
	bool cicluNegativ = false;

	for (int i = 0; i < n; i++)
		d[i] = 100000;
	d[0] = 0;

	Q.push(0); viz[0] = true;
	while (!Q.empty() && !cicluNegativ){
		int t = Q.front();
		Q.pop();

		viz[t] = false;

		for (size_t i = 0; i < G[t].size(); i++){
			int a = G[t][i].to;
			if ( d[a] > d[t] + G[t][i].cost){
				d[a] = d[t] + G[t][i].cost;
				if (!viz[a]){
					if (cntInQueue[a] > n)
						cicluNegativ = true;
					else{
						viz[a] = true;
						cntInQueue[a]++;
						Q.push(a);
					}
				}
			}
		}
	}


	ofstream fout ("bellmanford.out");
	if (cicluNegativ)
		fout << "Ciclu negativ!";
	else
		for (int i = 1; i < n; i++)
			fout << d[i] << ' ';
	fout.close();

	return 0;
}