//#include <iostream>
//#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include <algorithm>
//#include <utility>
#include <queue>

using namespace std;

//ifstream in ("bellmanford.in");
//ofstream out ("bellmanford.out");

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

vector < pair < int, int > > graf[MAXN];
int N, M;
int cost[MAXN];
int cnt[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;

//queue <int> Q;

inline void read (int &x)
{
	short neg = 1;
	
	while (*buffer < '0' || *buffer > '9'){
		if (*buffer == '-') neg = (-1);
		
		++buffer;
	}
	
	x = 0;
	
	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 nod;
	long long fs;
	
	fseek (stdin, 0, SEEK_END);
	fs = ftell (stdin);
	buffer = (char*) malloc (fs);
	rewind (stdin);
	fread (buffer, 1, fs, stdin);

	//in >> N >> M;
	read(N), read(M);
	//scanf ("%d %d", &N, &M);
	
	while (M--){
		//in >> x >> y >> cst;
		read(x), read(y), read(cst);
		//scanf ("%d %d %d", &x, &y, &cst);
		
		graf[x].push_back (make_pair (y, cst));
		//graf[y].push_back (make_pair (x, cst));
	}
	
	for (nod = 1; nod <= N; ++nod)
		cost[nod] = INF;
	
	cost[1] = 0;
	Q.push (1);
	
	while (!Q.empty ()){
		nod = Q.top ();
		//nod = Q.front ();
		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);
					++cnt[it -> first];
					
					if (cnt[it -> first] >= N){
						printf ("Ciclu negativ!");
						
						return 0;
					}
				}
				
			}
	}
	
	/*for (i = 1; i <= N; ++i)
		for (it = graf[i].begin (); it != graf[i].end (); ++it)
			if (cost[it -> first] > cost[i] + (it -> second)){
				//out << "Ciclu negativ!";
				printf ("Ciclu negativ!");
				
				return 0;
			}*/
	
	for (i = 2; i <= N; ++i)
		//out << cost[i] << " ";
		printf ("%d ", cost[i]);
	
	return 0;
}