#include <iostream>
#include <utility>
#include <vector>
#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 visited[NMAX], hasNegativeCycle = false;
int main() {
	read();
	bellmanFord(1);
	showDistances();
	return 0;
}
void read(){
	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++){
		cin >> from >> to >> cost;
		nodes[from].push_back(make_pair(to, cost));
	}
}
void bellmanFord(int node){
	for (int i = 2; i <= n; i++)
		dist[i] = std::numeric_limits<int>::max();
	visited[node] = true;
	int i = 0, changes = 1;
	while (i < n - 1 && changes > 0){
		changes = 0;
		for (int j = 1; j <= n; j++)
			if (visited[j]){
				visited[j] = false;
				for (int k = 0; k < nodes[j].size(); k++){
					int nextNode = nodes[j][k].first;
					int cost = nodes[j][k].second;
					if (dist[j] + cost < dist[nextNode]){
						dist[nextNode] = dist[j] + cost;
						visited[nextNode] = true;
						changes++;
					}
				}
			}
		i++;
	}
	if (changes > 0)
		hasNegativeCycle = true;
}
void showDistances(){
	if (hasNegativeCycle){
		cout << "Ciclu negativ!";
		return;
	}
	for (int i = 2; i <= n; i++)
		cout << dist[i] << " ";
}