// http://infoarena.ro/problema/bellmanford
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

#define INFINITY 0x3f3f3f3f
#define location first
#define cost second
int nodes,edges;

vector< list< pair<int,int> > > graph;
vector<int> dist;
vector<bool> inQueue;
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > myHeap;

void read();
bool bellmanFord(int startNode);
void write(bool cycle);

int main() {
	read();
	write(bellmanFord(1));

	return (0);
}

void read() {
	ifstream in("bellmanford.in");
	int from,to,cost;

	in >> nodes >> edges;
	graph.resize(nodes+1);
	dist.resize(nodes+1);
	inQueue.resize(nodes+1);

	for(int i=1;i<=edges;i++) {
		in >> from >> to >> cost;

		graph.at(from).push_back(make_pair(to,cost));
	}

	in.close();
}

bool bellmanFord(int startNode) {
	dist.assign(nodes+1,INFINITY);
	dist.at(startNode) = 0;

	int relaxed;
	list< pair<int,int> >::iterator neighbour;

	for(int step=1;step<nodes;step++) {
		relaxed = false;

		for(int currentNode=1;currentNode<=nodes;currentNode++)
			for(neighbour=graph.at(currentNode).begin();
				neighbour!=graph.at(currentNode).end();
				neighbour++)
				if(dist.at(neighbour->location) > dist.at(currentNode) + neighbour->cost) {
					dist.at(neighbour->location) = dist.at(currentNode) + neighbour->cost;
					relaxed = true;
				}

			if(!relaxed)
				break;
	}

	for(int step=1;step<nodes;step++) {
		relaxed = false;

		for(int currentNode=1;currentNode<=nodes;currentNode++)
			for(neighbour=graph.at(currentNode).begin();
				neighbour!=graph.at(currentNode).end();
				neighbour++)
				if(dist.at(neighbour->location) > dist.at(currentNode) + neighbour->cost)
					return false;	// exista ciclu negativ
	}

	return true;
}

void write(bool status) {
	ofstream out("bellmanford.out");

	if(status)
		for(int i=1;i<=nodes;i++)
			out << dist.at(i) << " ";
	else
		out << "Ciclu negativ!\n";

	out.close();
}