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

struct muc{
	int dest, cost;
	muc(const int a, const int b): dest(a), cost(b){} };

const int inf = 1000000000;

bool bellman_ford(const vector<vector<muc> >& graf, vector<int>& dist){
	const int n = graf.size();
	queue<int> q;
	vector<bool> in_q(n, false);
	vector<int> nr_viz(n, 0);

	q.push(0);
	in_q[0] = true;

	while(!q.empty()){
		const int cur = q.front();
		q.pop();
		in_q[cur] = false;

		++nr_viz[cur];
		if(nr_viz[cur] > n+1){
			return false; }

		for(int i = 0; i < graf[cur].size(); ++i){
			const int next = graf[cur][i].dest, len = graf[cur][i].cost;
			if(dist[next] > len + dist[cur]){
				dist[next] = len + dist[cur];
				if(!in_q[next]){
					q.push(next);
					in_q[next] = true; } } } }
	return true; }

int main(){
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");

	int n, m;

	f >> n >> m;

	vector<vector<muc> > graf(n);

	for(int i = 0, x, y, c; i < m; ++i){
		f >> x >> y >> c;
		--x, --y;
		graf[x].push_back(muc(y, c)); }

	vector<int> dist(n, inf);
	dist[0] = 0;

	if(bellman_ford(graf, dist)){
		for(int i = 1; i < n; ++i){
			g << dist[i] << ' '; } }
	else{
		g << "Ciclu negativ!"; }

	return 0; }