#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

#define MAXN 50000
#define MAXM 250000
#define MAXC 1000

struct edge{
  int pos, cost;
};

struct nodes{
  int dist;
  vector <edge> edges;
};

nodes graph[MAXN + 1];
int graphSize;

queue <int> q;
bool inQ[MAXN + 1];

void addEdge(int a, int b, int cost) {
  graph[a].edges.push_back({b, cost});
}

bool bfs(int pos) {
  int cPos, i;

  for ( i = 1; i <= graphSize; i++ ) {
    graph[i].dist = MAXM * MAXC + 1;
  }

  q.push(pos);
  graph[pos].dist = 0;

  while ( q.size() && graph[pos].dist >= 0 ) {
    cPos = q.front();
    inQ[cPos] = false;

    for ( edge node : graph[cPos].edges ) {
      if ( graph[node.pos].dist > graph[cPos].dist + node.cost ) {
        if ( inQ[node.pos] == false ) {
          inQ[node.pos] = true;
          q.push(node.pos);
        }

        graph[node.pos].dist = graph[cPos].dist + node.cost;
      }
    }

    q.pop();
  }

  return graph[pos].dist >= 0;
}

int main() {
  FILE *fin, *fout;
  fin = fopen("bellmanford.in", "r");
  fout = fopen("bellmanford.out", "w");

  int m, i, a, b, c;
  bool notaCycle;

  fscanf(fin, "%d%d", &graphSize, &m);

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d%d", &a, &b, &c);

    addEdge(a, b, c);
  }

  notaCycle = bfs(1);

  if ( notaCycle ) {
    for ( i = 2; i <= graphSize; i++ ) {
      fprintf(fout, "%d ", graph[i].dist);
    }
    fprintf(fout, "\n");
  } else {
    fprintf(fout, "Ciclu negativ!\n");
  }

  fclose(fin);
  fclose(fout);
  return 0;
}