///BELLMAN-FORD
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> Edge;

const int INF = numeric_limits<int>::max();

bool bellmanFord(vector<vector<Edge> >& adjList, vector<int>& answ) {
	vector<int> numrel(adjList.size(), 0);
	vector<bool> inQueue(adjList.size(), false);
	
	answ.assign(adjList.size(), INF);
	answ[0] = 0;

	queue<int> q;
	q.push(0);
	
	inQueue[0] = true;
	++numrel[0];

	int cr, crCost;
	vector<Edge>::iterator i;
	while(!q.empty()) {
		cr = q.front();
		///crCost = q.front().second;
		inQueue[cr] = false;
		q.pop();

		for(i=adjList[cr].begin(); i!=adjList[cr].end(); ++i) 
			if(answ[cr] + i->second < answ[i->first]) {
				answ[i->first] = answ[cr] + i->second;
				
				if(!inQueue[i->first]) {
					q.push(i->first);
					inQueue[i->first] = true;
					++numrel[i->first];

					if(numrel[i->first] >= adjList.size()) 
						return true;
				}
			}
	} 	

	return false;
}

int main() {
	ifstream inStr("bellmanford.in");
	ofstream outStr("bellmanford.out");

	int N, M;
	inStr >> N >> M;

	vector<vector<Edge> > adjList(N);
	
	int fr, to, cst;
	for(int i=0; i<M; ++i) {
		inStr >> fr >> to >> cst;
		adjList[--fr].push_back(Edge(--to, cst));
	}

	vector<int> answ;
	bool isNegCycle = bellmanFord(adjList, answ);

	if(!isNegCycle) {
		for(int i=1; i<answ.size(); ++i)
			if(answ[i] != INF)
				outStr << answ[i] << ' ';
			else 
				outStr << 0 << ' ';
	} else outStr << "Ciclu negativ!";

	outStr << '\n';

	return 0;
}