//
//  main.cpp
//  bellman ford
//
//  Created by Eusebiu Rares on 28/08/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"
#include "vector"
#include "queue"

std::fstream in ("bellmanford.in", std::ios::in) ;
std::fstream out ("bellmanford.out", std::ios::out) ;

const int MV = 5e4 ;
const int INF = 1e9 ;

std::vector<std::pair<int, int> > G[MV + 1] ;
int negativeCycle ;

int cost[MV + 1] ;
int seen[MV + 1] ;
int sawTime[MV + 1] ;

void bellmanFord(int source, int size) {
	std::queue<int> Q ;
	Q.push(source) ;
	seen[source] = 1 ;
	while (!Q.empty()) {
		int vertexStart = Q.front() ;
		Q.pop() ;
		seen[vertexStart] = 0 ;
		for (auto edge : G[vertexStart]) {
			if (cost[edge.first] > cost[vertexStart] + edge.second) {
				if (sawTime[vertexStart] == size - 1) {
					negativeCycle = 1 ;
					return ;
				} else {
					cost[edge.first] = cost[vertexStart] + edge.second ;
					sawTime[edge.first] = sawTime[vertexStart] + 1 ;
					if (!seen[edge.first]) {
						seen[edge.first] = 1 ;
						Q.push(edge.first) ;
					}
				}
			}
		}
	}
}

int main(int argc, const char * argv[]) {
	int n, m ;
	in >> n >> m ;
	for (int i = 1 ; i <= m ; ++ i) {
		int x, y, cost ; in >> x >> y >> cost ;
		G[x].push_back(std::make_pair(y, cost)) ;
	}
	for (int i = 2 ; i <= n ; ++ i) {
		cost[i] = INF ;
	}
	bellmanFord(1, n) ;
	if (negativeCycle == true) {
		out << "Ciclu negativ!" ;
	} else {
		for (int i = 2 ; i <= n ; ++ i) {
			out << cost[i] << ' ' ;
		}
	}
}