#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

#define MAX_N 50004

struct Edge {
  int node, cost;
};

vector<Edge> graph[MAX_N];

queue<int> bfsQueue;
int dist[MAX_N];
int contor[MAX_N];
int m, stop;

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

void bfs(int node) {
  int qFront;

  bfsQueue.push(node);
  dist[node] = 0;
  stop = 0;
  while (!bfsQueue.empty() && stop == 0) {
    qFront = bfsQueue.front();
    contor[qFront]++;
    if(contor[qFront]<m){
      for (const Edge& edge : graph[qFront])
        if (!dist[edge.node] || dist[edge.node] > dist[qFront] + edge.cost) {
          bfsQueue.push(edge.node);
          dist[edge.node] = dist[qFront] + edge.cost;
        }
    }else{
      stop = 1;
    }
    bfsQueue.pop();
  }

}

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

  int n, i, a, b, cost;
  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; ++i) {
    fscanf(fin, "%d%d%d", &a, &b, &cost);
    addEdge(a, b, cost);
  }

  bfs(1);
  if(stop==1){
    fprintf(fout,"Ciclu negativ!");
  }else{
    for (i = 2; i <= n; ++i)
      fprintf(fout, "%d ", dist[i]);
  }


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