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

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
int number[50001], dist[50001];
bool viz[50001];
vector<edge> graf[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(z, y));
}

void solve()
{
  queue<int> q;
  memset(viz, false, sizeof(viz));
  viz[1] = true;
  q.push(1);

  for(int i = 2;i <= n;++i)
    dist[i] = oo;

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

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


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