#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define DIM 50000
#define INF (1LL << 30)
typedef pair<int, int> PII;

bool ciclu;   
int n, m;
bool sel[DIM + 1];       //ce elemente am in coada;
int cost[DIM + 1];       //costul pana la fiecare element;
int fr[DIM + 1];         //de cate ori am ajuns in fiecare element;
vector <PII> G[DIM + 1];
queue <int> Q;

static inline void BellmanFord(int st) {
  for(int i = 1; i <= n; i++)
    cost[i] = INF;

  Q.push(st);
  cost[st] = 0;
  sel[st] = 1;
  while(!Q.empty()) {
    int nod = Q.front();
    int c = cost[nod];

    sel[nod] = 0;         //scot nodul din coada;
    Q.pop();

    fr[nod]++;
    if(fr[nod] == n) {    //daca am ciclu nu are rost sa mai continui;
      ciclu = 1;
      return;
    }

    for(auto e : G[nod])
      if(c + e.second < cost[e.first]) {    //daca am un drum mai mic;
        cost[e.first] = c + e.second;
        sel[e.first] = 1;
        Q.push(e.first);
      }
  }
}

int main() {
  fin.tie(0);
  fout.tie(0);
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int x, y, c;

    fin >> x >> y >> c;
    G[x].push_back({y, c});
  }

  BellmanFord(1);

  if(!ciclu)
    for(int i = 2; i <= n; i++)
      fout << cost[i] << " ";
  else fout << "Ciclu negativ!";

  return 0;
}