#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

const int MAXN = 50010;
const int INF = 1 << 30;

vector < pair < int, int > > graf[MAXN];
int N, M;
int cost[MAXN];
bool viz[MAXN];
char *buffer;

struct comp
{
	inline bool operator () (const int &a, const int &b){
		return cost[a] > cost[b];
	}
};

priority_queue < int, vector <int>, comp > Q;

void BF ()
{
	vector < pair < int, int > > :: iterator it;
	int nod;
	
	for (nod = 1; nod <= N; ++nod)
		cost[nod] = INF;
	
	cost[1] = 0;
	Q.push (1);
	
	while (!Q.empty ()){
		nod = Q.top ();
		Q.pop ();
		viz[nod] = 0;
		
		for (it = graf[nod].begin (); it != graf[nod].end (); ++it)
			if (cost[it -> first] > cost[nod] + (it -> second)){
				cost[it -> first] = cost[nod] + (it -> second);
				
				if (!viz[it -> first]){
					viz[it -> first] = 1;
					Q.push (it -> first);
				}
			}
	}
}

inline void read (int &x)
{
	int neg = 1;
	
	while (*buffer < '0' || *buffer > '9'){
		++buffer;
		
		if (*buffer == '-') neg = (-1);
	}
	
	while (*buffer >= '0' && *buffer <= '9'){
		x = (x * 10) + (*buffer - '0');
		++buffer;
	}
	
	x *= neg;
}

int main ()
{
	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);
	
	vector < pair < int, int > > :: iterator it;
	int x, y, cst, i;
	int fs;
	bool ok = 0;
	
	fseek (stdin, 0, SEEK_END);
	fs = ftell (stdin);
	buffer = (char*) malloc (fs);
	rewind (stdin);
	fread (buffer, 1, fs, stdin);
	
	read(N), read(M);
	
	while (M--){
		//in >> x >> y >> cst;
		read(x), read(y), read(cst);
		
		graf[x].push_back (make_pair (y, cst));
		graf[y].push_back (make_pair (x, cst));
	}
	
	for (i = 1; i <= N; ++i)
		for (it = graf[i].begin (); it != graf[i].end (); ++it)
			if (cost[it -> first] > cost[i] + (it -> second)){
				ok = 1;
				break;
			}
			
	if (ok){
		//out << "Ciclu negativ";
		printf ("Ciclu negativ!");
		
		return 0;
	}
	
	for (i = 1; i <= N; ++i)
		//out << cost[i] << " ";
		printf ("%d ", cost[i]);
	
	return 0;
}