#include <stdio.h>
#include <fstream>
#include <vector>

#define INF 1<<30

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int N, M;
vector< vector< pair<int,int> > > neigh;
vector<int> d;
vector< pair<int,int> > edges;

void read(){

	in >> N >> M;

	d.resize(N+1);
	d.assign(N+1, INF);

	for(int i = 0; i <= N; ++i){
		vector< pair<int,int> > v;
		neigh.push_back(v);
	}

	int x, y, c;
	for(int i = 0; i < M; ++i){
		in >> x >> y >> c;
		neigh[x].push_back(make_pair(y,c));
		edges.push_back(make_pair(x,y));
		if(x == 1)
			d[y] = c;
	}
	d[1] = 0;
}


int BellmanFord(int s){

	for(int k = 1; k <= N-2; ++k){
		for(int i = 1; i <= N; ++i){
			for(unsigned int j = 0; j < neigh[i].size(); ++j){
				int u = i;
				int v = neigh[i][j].first;
				int c = neigh[i][j].second;
				int dist = d[u] + c;
				if(d[v] > dist)
					d[v] = dist;
			}
		}
		
	}

	for(int i = 1; i <= N; ++i){
		for(unsigned int j = 0; j < neigh[i].size(); ++j){
			int u = i;
			int v = neigh[i][j].first;
			int c = neigh[i][j].second;
			int dist = d[u] + c;
			if(d[v] > dist)
				return -1;
		}
	}

	return 0;

}



int main(){

	read();
	int rez = BellmanFord(1);

	if(rez == -1)
		out << "Ciclu negativ!";
	else{
		for(unsigned int i = 2; i < d.size(); ++i){
			if(d[i] == INF) d[i] = 0;
			out << d[i] << " ";
		}
	}
}