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

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
vector<edge1> graf[50001];
int number[50001], dist[50001];
bool viz[50001];

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

void solve()
{
  memset(dist, oo, sizeof(dist));
  dist[1] = 0;
  queue<int> q;
  q.push(1);

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

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

int main()
{
  read();
  solve();
  return 0;
}