#include <fstream>
#include <cstdlib>

using namespace std;

int n, m;
int d[50001];

struct edge{
	int u, v, c;
};

edge *head;

int main(){
	ifstream f("bellmanford.in");
	f >> n >> m;
	head = (edge*)malloc(m*sizeof(edge));
	int u, v, c;
	for(int i=0; i<m; i++){
		f >> u >> v >> c;
		head[i] = {u, v, c};
	}
	f.close();
	
	for(int i=1; i<=n; i++) d[i] = 10000000;
	d[1] = 0;
	
	for(int i=1; i<=n-1; i++){
		for(int j=0; j<m; j++){
			if(d[head[j].u] + head[j].c < d[head[j].v]) d[head[j].v] = d[head[j].u] + head[j].c;
		}
	}
	
	ofstream g("bellmanford.out");
	
	for(int i=0; i<m; i++)
		if(d[head[j].u] + head[j].c < d[head[j].v]){
			g << "Ciclu negativ!";
			g.close();
			return 0;
		}
		
	for(int i=1; i<=n; i++) g << d[i] << " ";
	
	g.close();
	free(head);
	return 0;
}