#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
#define NMAX 50005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
void read();
void bellmanFord(int node);
void showDistances();
vector<pair<int, int> > nodes[NMAX];
int n, m;
int dist[NMAX];
bool inQueue[NMAX], hasNegativeCycle = false;
int main() {
	read();
	bellmanFord(1);
	showDistances();
	return 0;
}
void read(){
	f >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++){
		f >> from >> to >> cost;
		nodes[from].push_back(make_pair(to, cost));
	}
}
void bellmanFord(int startNode){
	for (int i = 2; i <= n; i++)
		dist[i] = std::numeric_limits<int>::max();
	inQueue[startNode] = true;
	queue <int> q;
	q.push(startNode);
	int i = 0, changes = 1;
	while (i < n - 1 && changes > 0){
		changes = 0;
		for (int ii = 0; ii < q.size(); ii++){
			int node = q.front();
			q.pop();
			inQueue[node] = false;
			for (int j = 0; j < nodes[node].size(); j++){
				int nextNode = nodes[node][j].first;
				int cost = nodes[node][j].second;
				if (dist[node] + cost < dist[nextNode]){
					dist[nextNode] = dist[node] + cost;
					if (!inQueue[nextNode]){
						q.push(nextNode);
						inQueue[nextNode] = true;
					}
					changes++;
				}
			}
		}
		i++;
	}
	if (changes > 0)
		hasNegativeCycle = true;
}
void showDistances(){
	if (hasNegativeCycle){
		g << "Ciclu negativ!";
		return;
	}
	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";
}