#include <bits/stdc++.h>
#define dimn 50005
#define inf INT_MAX>>1
#define mp std::make_pair
using data = std::pair <int, int>;

std::ifstream f("bellmanford.in");
std::ofstream g("bellmanford.out");
//#define f std::cin
//#define g std::cout

int N, M;
int cost[dimn];
std::vector <data> adj[dimn];
 
bool is_queued[dimn], bad;
int times[dimn];
std::queue <int> q;
void bellmanford() {
	cost[1] = 0;
	for (int i=2; i<=N; i++)
	    cost[i] = inf;
 
	q.push(1); is_queued[1] = true;
	int x, dist, pres;
	while(!q.empty() && !bad) {
		pres = q.front();
		q.pop();
		is_queued[pres] = 0;
		
		for (auto it:adj[pres]) {
			x = it.first;
			dist = it.second;
			
			if (cost[x] > dist + cost[pres]) {
				cost[x] = dist + cost[pres];
				if(!is_queued[x]) {
					if (times[x]>N) 
						bad = true;
					else {
						times[x]++;
						is_queued[x] = 1;
						q.push(x);
					}
				}
			}
		}
	}
}
 
void citire() {
    f >> N >> M;
    for(int i=0, a, b, c; i<M; i++) {
        f >> a >> b >> c; 
        adj[a].push_back(mp(b, c));
	}
}
void rezolvare() {
    bellmanford();
    if(bad)
    	g << "Ciclu negativ!" ;
    else {
    	for (int i=2; i<=N; i++)
    		g << cost[i] << " " ;
    	g << "\n" ;
    }
}

int main()
{
    citire();
    rezolvare();

    return 0;
}