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

#define NMAX 50001
#define COST_MAX 1<<29

int N, M, distances[NMAX], times_seen[NMAX];
list<pair<int, int> > adj_list[NMAX];
queue<int> q; 
bool queued[NMAX];

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(s); queued[s] = true;
  while (!q.empty()) {
    int u = q.front(); q.pop(); queued[u] = false;
    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[it->first] = true;          
        }
      }
    }
  }
  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;
}