#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Muchie
{
  int vecin, cost;
};

struct Nod
{
  int dm, nrm;
} d[50005];
vector <Muchie> v[50005];
queue <int> c;
int n, m;

void bellman(int);

int main()
{
  int i, a, b, c;
  fin>>n>>m;
  for(i=1; i<=m; i++)
  {
    fin>>a>>b>>c;
    v[a].push_back({b, c});
  }
  for(i=2; i<=n; i++)
  {
    d[i].dm=1e9;
  }
  bellman(1);
}

void bellman(int nod)
{
  int i, p;
  c.push(nod);
  while(!c.empty())
  {
    p=c.front();
    for(i=0; i<v[p].size(); i++)
    {
      if(d[v[p][i].vecin].dm>(d[p].dm+v[p][i].cost))
      {
        d[v[p][i].vecin].dm=d[p].dm+v[p][i].cost;
        d[v[p][i].vecin].nrm++;
        if(d[v[p][i].vecin].dm==n)
        {
          fout<<"Ciclu negativ!"<<'\n';
          return;
        }
        c.push(v[p][i].vecin);
      }
    }
    c.pop();
  }
  for(i=2; i<=n; i++)
  {
    fout<<d[i].dm<<' ';
  }
  fout<<'\n';
}