#include <bits/stdc++.h>
 
using namespace std;
 
const int kMaxN = 50000;
const int kInf = numeric_limits<int>::max();
 
int n, m;
int D[kMaxN + 1];
vector<pair<int, int> > G[kMaxN + 1];
vector<int> cnt_in_queue(kMaxN, 0);
bool negative_cycle = false;

void bellman_ford(int s)
{ 
	queue<int> Q;
	bitset <kMaxN> in_queue(false);
		
	D[s] = 0;
	Q.push(s);
	in_queue[s].flip();
	
	while(!Q.empty() & !negative_cycle) {
		int tmp = Q.front();
		Q.pop();
		in_queue[tmp] = false;
		vector < pair<int, int> >::iterator it;
		for (it = G[tmp].begin(); it != G[tmp].end(); ++it) 
			if (D[tmp] < kInf) 
				if (D[it->first] > D[tmp] + it->second) {
					D[it->first] = D[tmp] + it->second;
					if(!in_queue[it->first]) {	
						if(cnt_in_queue[it->first] > n)
							negative_cycle = true;	    		
						else {
							Q.push(it->first);
							in_queue[it->first] = true;
							cnt_in_queue[it->first]++;
						}
					}
				}
	}
}		
 
int main()
{	
	//clock_t tStart = clock();

    	freopen("bellmanford.in", "rt", stdin);
    	freopen("bellmanford.out", "wt", stdout);
 
    	scanf("%d %d", &n, &m);
 
    	for (int i = 1; i <= n; ++i) D[i] = kInf;
 
    	for (int i = 0; i < m; ++i) {
        	int a, b, d;
        	scanf("%d %d %d", &a, &b, &d);
        	G[a].push_back(make_pair(b, d));
    	}
     
	bellman_ford(1);
	if (!negative_cycle) { 
    		for (int i = 2; i <= n; ++i)
			printf("%d ", D[i]);
		printf("\n");
	} else 
    		printf("Ciclu negativ!\n");
//	printf("Time: %.4fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);  

	return 0;
}