#include <fstream>
#include <iostream>
#include <queue>
#include <limits.h>
#include <utility>
#include <string.h>

#define NMAX 50004
#define INF (LLONG_MAX - 2000)

typedef std::pair<int, int> Link;
typedef std::pair<Link, int> Edge;
typedef std::vector<Edge> EdgeContainer;
long long d[NMAX];
bool in_list[NMAX];

EdgeContainer neighbors[NMAX];

int main () {
	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");

	int n, m, x, y, cost, i;
	fin >> n >> m;

	for (i = 2; i <= n; i++) {
		d[i] = INF;
	}

	for (i = 1; i <= m; i++) {
		fin >> x >> y >> cost;
		neighbors[x].push_back(Edge(Link(x, y), cost));
	}

	d[1] = 0;
	bool stop = false;
	std::queue<int> to_update;
	std::vector<int> times_in_list(NMAX, 0);
	to_update.push(1);
	in_list[1] = true;

	while (!to_update.empty() && !stop) {
		x = to_update.front();
		to_update.pop();
		in_list[x] = false;
		for (std::vector<Edge>::iterator it = neighbors[x].begin();
			it != neighbors[x].end(); it++) {

			y = it->first.second;
			if (d[y] > d[x] + it->second) {
				d[y] = d[x] + it->second;
				if (!in_list[y]) {
                    if (times_in_list[y] <= n){
                        to_update.push(y);
                        in_list[y] = true;
                        times_in_list[y] ++;
                    }
                    else {
                        stop = true;
                    }
                }
			}			
		}
	}

	if (stop) {
		fout << "Ciclu negativ!\n";
		return 0;
	}

	for (i = 2; i <= n; i++) {
		if (d[i] == INF) {
			fout << "0 ";
		} else {
			fout << d[i] << ' ';
		}
	}
	fout << "\n";

	return 0;
}