#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector <int> distante[500000];
vector <int> nod[500000];
int v[500000];
int main()
{
  int n, m, a, b, cost, ok=1;
  fin>>n>>m;
  for (int i=1;i<=m;i++)
  {
    fin>>a>>b>>cost;
    nod[a].push_back(b);
    distante[a].push_back(cost);
  }
  v[1]=0;
  for (int i=2;i<=n;i++)
    v[i]=500000;
  for (int i=1;i<=n-1;i++)
    for (int j=1;j<=n;j++)
      for (int z=0;z<distante[j].size();z++)
        if (v[j]+distante[j][z]<v[nod[j][z]])
        {
          v[nod[j][z]]=v[j]+distante[j][z];
        }

    for (int j=1;j<=n;j++)
      for (int z=0;z<distante[j].size();z++)
        if (v[j]+distante[j][z]<v[nod[j][z]])
        {
          ok=0;
        }
  if (ok==1)
    for (int i=2;i<=n;i++)
      fout<<v[i]<<" ";
  else fout<<"Ciclu negativ!";
  fout<<endl;
  return 0;
}