#include <iostream>
#include <vector>
#include <utility>

#define MAX 1001

using namespace std;

int n, m, u, v, w;

class Node{
public:
	int parent, dist;
	Node(int p, int d): parent(p), dist(d) {}
};
class Trio{
public:
	int u, v, w;
	Trio(int uu, int vv, int ww) : u(uu), v(vv), w(ww) {}
};


vector< Trio* > edges;
vector < Node* >  nodes;

bool bellman_ford(){
	for (int i = 0; i < n - 1; i++){
		for (int j = 0; j < m; j++){
			Trio *t = edges[j];
			if (nodes[t->v]->dist > (nodes[t->u]->dist + t->w)){
				nodes[t->v]->dist = nodes[t->u]->dist + t->w;
				nodes[t->v]->parent = t->u;
			}
		}
	}
	for (int j = 0; j < m; j++){
		Trio *t = edges[j];
		if (nodes[t->v]->dist >(nodes[t->u]->dist + t->w)){
			return false;
		}
	}
	return true;
}

int main(){
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	
	nodes.push_back(new Node(-1, 0));
	for (int i = 1; i < n; i++)
		nodes.push_back(new Node(-1, MAX));
	
	for (int i = 0; i < m; i++){
		scanf("%d%d%d", &u, &v, &w);
		//cin >> u >> v >> w;
		u--; v--;
		edges.push_back(new Trio(u, v, w));
	}
	if (!bellman_ford()) cout << "Ciclu negativ!\n";
	else
	for (int i = 1; i < n; i++)
		cout << nodes[i]->dist << " ";
	cout << "\n";
	return 0;
}