#include <bits/stdc++.h>
#define edge pair<int, int>
#define node first
#define cost second

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

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()
{
  queue<int> q;
  q.push(1);
  memset(dist, 0x3f3f3f3f, sizeof(dist));
  dist[1] = 0;

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

    for(auto it : graf[nod])
      if(dist[it.node] > dist[nod] + it.cost)
        {
          dist[it.node] = dist[nod] + it.cost;
          if(!viz[it.node]) q.push(it.first);
          viz[it.node] = true;
          nr[it.node]++;

          if(nr[it.node] >= n)
            {
              g<<"Ciclu negativ!";
              return;
            }
        }
    viz[nod] = false;
  }
  for(int i = 2;i <= n;++i)
    g<<dist[i]<<" ";
}

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