#include <fstream>
#include <queue>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct edge{
	int from, to, cost;
}edges[250000];

int v, e;
int dist[50000];
int ap[50000];

queue<int> q;

int main(){
	fin >> v >> e;
	for(int i = 0; i < e; i++)
		fin>>edges[i].from>>edges[i].to>>edges[i].cost;

	for(int i=0;i<v;i++)
		dist[i]=1001;

	while(!q.empty()){
		for(int edge = 0; edge < e; edge++){
			int weight = edges[edge].cost;
			int from = edges[edge].from;
			int to = edges[edge].to;

			if(dist[from] + weight < dist[to]){
				dist[to] = dist[from] + weight;
				q.push(to);
				ap[to]++;
			}
		}
		q.pop();
	}

	for(int i=0;i<v;i++)
		if(ap[i]==v){
			fout<<"Ciclu negativ!\n";
			return 0;
		}
	for(int i=1;i<v;i++)
		fout<<dist[i]<<" ";
	fout<<"\n";
	return 0;
}