#include <cstdio>
#include <list>
#include <queue>
#include <bitset>
using namespace std;

#define NMAX 50001
#define COST_MAX 1001

int N, M, distances[NMAX], times_seen[NMAX];
list<pair<int, int> > adj_list[NMAX];
queue<int> q; bitset<NMAX> queued(false);

void readInput() {
	int from, to, cost;
	freopen("bellmanford.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (int i=0;i<M;i++) {
		scanf("%d %d %d",&from,&to,&cost);		
    adj_list[from].push_back(make_pair(to,cost));
	}	
}

bool bellman_ford(int s) {
  list<pair<int,int> >::iterator it;
  for (int i=1;i<=N;i++) distances[i] = COST_MAX;
	distances[s] = 0;
  q.push(1); queued.flip(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(); queued.flip(u);
    for (it=adj_list[u].begin();it!=adj_list[u].end();it++) {
      if (distances[it->first] > distances[u]+it->second) {
        distances[it->first] = distances[u]+it->second;
        if (!queued[it->first]) {
          if (++times_seen[it->first] > N) {
            return false;
          }
          q.push(it->first); 
          queued.flip(it->first);
        }
      }
    }
  }
	return true;
}

int main() {
	readInput();	
	freopen("bellmanford.out","w",stdout);
	if (bellman_ford(1)) {
		for (int i=2;i<=N;i++) {
			printf("%d ",distances[i]);
		}
	}
	else {
		printf("Ciclu negativ!");
	}
	printf("\n");
	return 0;
}