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

#define INFINITY 0x3f3f3f3f
#define maxSize 50001
#define location first
#define cost second

int nodes;
int timesVisited[maxSize];
bool visit[maxSize];
vector<int> dist(maxSize,INFINITY);
vector< pair<int,int> > graph[maxSize];
queue<int> myQueue;

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


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

	return (0);
}

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

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

		graph[from].push_back(make_pair(to,cost));	// graf orientat
	}

	in.close();
}

bool bellmanFord(int startNode) {
	dist[startNode] = 0;

	int currentNode;
	vector< pair<int,int> >::iterator neighbour,end;

	myQueue.push(startNode);	// se introduce nodul se start in coada

	while(!myQueue.empty()) {
		currentNode = myQueue.front();	// se extrage primul nod
		end = graph[currentNode].end();

		for(neighbour=graph[currentNode].begin();neighbour!=end;++neighbour)
			// daca se poate imbunatatii costul
			if(dist[neighbour->location] > dist[currentNode] + neighbour->cost) {
				dist[neighbour->location] = dist[currentNode] + neighbour->cost;

				// daca nodul al carui cost a fost imbunatatit nu a fost vizitat
				if(!visit[neighbour->location]) {
					timesVisited[neighbour->location]++;	// creste numarul de vizitari

					if(timesVisited[neighbour->location] > nodes)
						return false;	// graful are ciclu negativ
				}

				myQueue.push(neighbour->location);	// se introduce in coada nodul al carui cost a fost imbunatatit
				visit[neighbour->location] = true;	// se marcheaza ca vizitat
			}

		visit[currentNode] = false;	// se marcheaza ca nevizitat nodul curent
		myQueue.pop();	// se elimina din coada
	}

	return true;	// graful nu are ciclu negativ
}

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

	if(status)
		for(int i=2;i<=nodes;i++)
			out << dist[i] << " ";
	else
		out << "Ciclu negativ!\n";

	out.close();
}