#include <fstream>
#include <vector>
using namespace std;

long N,M;

long Distante[50005];
vector<pair<int,int> *> *Muchii;

long DeVerificat1[50005];
long DeVerificat2[50005];
long Check[50005];

long NVer1;
long NVer2;
long *VerC;
long *VerN;

int main(void)
{
 long i,a,b,d,j,l;
 long better;
 fstream fin("bellmanford.in",ios::in);
 fstream fout("bellmanford.out",ios::out);
 Muchii = new vector<pair<int,int> *>[50005];
 fin >> N >> M;
 for (i = 0;i < M;i += 1)
  {
   fin >> a >> b >> d;
   Muchii[a].push_back(new pair<int,int>(b,d));
  }
 for (i = 1;i <= N;i += 1)
  {
   Distante[i] = 60000000;
  }
 VerC = DeVerificat1;
 VerN = DeVerificat2;
 NVer1 = 1;
 NVer2 = 0;
 VerC[0] = 1;
 Distante[1] = 0;
 for (i = 2;i <= N;i += 1)
  {
   better = 0;
   memset(Check,0,50005 * sizeof(long));
   for (j = 0;j < NVer1;j += 1)
    {
     long from,to;
     from = VerC[j];
     for (l = 0;l < Muchii[from].size();l += 1)
      {
       if ((Distante[from] + Muchii[from][l]->second) < Distante[Muchii[from][l]->first])
         {
          Distante[Muchii[from][l]->first] = Distante[from] + Muchii[from][l]->second;
          if (Check[Muchii[from][l]->first] == 0)
            {
             VerN[NVer2] = Muchii[from][l]->first;
             NVer2 += 1;
             Check[Muchii[from][l]->first] = 1;
             better = 1;
            }
         }
      }
    }
   NVer1 = NVer2;
   NVer2 = 0;
   long *TTT = VerC;
   VerC = VerN;
   VerN = TTT;
  }
 if (better == 1)
   {
    fout << "Ciclu negativ!\n";
   }
  else
   {
    for (i = 2;i <= N;i += 1)
     {
      if (Distante[i] == 60000000)
        {
         Distante[i] = 0;
        }
      fout << Distante[i] << " ";
     }
   }
 fin.close();
 fout.close();
 return 0;
}