#include <bits/stdc++.h>

using namespace std;

const int maxN = 5e4 + 5, maxM = 25e4 + 5, INF = 0x3f3f3f3f;
int N, M;

struct Edge{
  int node, cost;
};
vector <Edge> G[maxN];
queue <int> q;
int dist[maxN], nr[maxN];
bool inq[maxN];

bool BellmanFord(int source){
  memset(dist, INF, sizeof(dist));
  dist[source] = 0;
  q.push(source);
  inq[source] = true;
  nr[source] = 1;

  while (!q.empty()){
    int node = q.front();
    inq[node] = false;
    q.pop();

    for (int i = 0; i < G[node].size(); i++){
      int son = G[node][i].node, cost = G[node][i].cost;
      if (cost + dist[node] < dist[son]){
        dist[son] = dist[node] + cost;
        if (!inq[son]){
          q.push(son);
          inq[son] = true;
          nr[son] ++;
          if (nr[son] > N)
            return N;
        }
      }
    }
  }
  return true;
}

int main(){
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);

  int x, y, z;
  scanf("%d %d", &N, &M);

  for (int i = 1; i <= M; i++){
    scanf("%d %d %d", &x, &y, &z);
    G[x].push_back({y, z});
  }

  if (BellmanFord(1) == false)
    printf("Ciclu negativ!");
  else{
    for (int i = 2; i <= N; i++)
      if (dist[i] == INF)
        printf("0 ");
      else
        printf("%d ", dist[i]);
  }


  return 0;
}