#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int, int> > x[200001];
int n, d[50001], nr[50001];
bool p[50001], cn;

void F(int nod)
{queue<int> q;
 q.push(nod);
 d[nod]=0;
 nr[nod]=1;
 p[nod]=1;

 while(q.empty()!=1 && cn==false)
 {nod=q.front();

  vector<pair<int, int> >:: iterator I;
  for(I=x[nod].begin();I<x[nod].end();I++)
  {int a=I->first, c=I->second;
   p[a]=0;

   if(d[a]>d[nod]+c)
   {d[a]=d[nod]+c;

    if(p[a]==0)
    {p[a]=1;
     nr[a]++;

     if(nr[a]==n)cn=1;
     q.push(a);
    }
   }
  }
  q.pop();
 }
}

int main()
{   int m, a, b, c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {fin>>a>>b>>c;
     x[a].push_back({b, c});
    }

    fill(d+1, d+1+n, 1e9);

    F(1);
    if(cn==0)
    {for(int i=2;i<=n;i++)
     fout<<d[i]<<" ";
    }
    else fout<<"Ciclu negativ!";

    return 0;
}