#include <bits/stdc++.h>
#define oo 0x3f3f3f3f 
#define edge pair<int, int>
#define nod first
#define cost second
#define dim 50000

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m, x, y, cost;
bool viz[dim + 5];
int nr[dim + 5], dist[dim + 5];
vector<edge> graf[dim + 5];

void Read()
{
  f>>n>>m;
  for(int i = 1;i <= m;++i)
    f>>x>>y>>cost, graf[x].push_back(make_pair(y, cost));
}

void bellman_ford()
{
  for(int i = 2;i <= n;++i) dist[i] = oo;
  queue<int> q;
  q.push(1);
  viz[1] = true;

  while(!q.empty())
  {
    int nod = q.front();

    for(auto it : graf[nod])
      if(dist[it.nod] > dist[nod] + it.cost)
      {
        dist[it.nod] = dist[nod] + it.cost;
        if(!viz[it.nod]) q.push(it.nod);
        viz[it.nod] = true;
        nr[it.nod]++;
        if(nr[it.nod] >= n)
          {
            g<<"Ciclu negativ!";
            return;
          }
      }
    q.pop();
    viz[nod] = false;
  }
  for(int i = 2;i <= n;++i)
    g<<dist[i]<<" ";
}

int main()
{
  Read();
  bellman_ford();
  return 0;
}