#include <fstream>
#include <queue>
#include <vector>
#define INF (int)2e9

using namespace std;

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

struct vect {
     int vf,cost;
}aux;

vector <vect> lista[50000];
queue <int> coada;

int n,m,i,c,x,y,dr,ciclu=0,z;
int d[50000],in[50000],up[50000];

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
         fin>>x>>y>>aux.cost;
         aux.vf=y;
         lista[x].push_back(aux);
    }
    for (i=1;i<=n;i++)
    {
         d[i]=INF;
    }

    d[1]=0;
    coada.push(1);
    while (!coada.empty() && !ciclu)
    {
         x=coada.front();
         coada.pop();
         in[x]=0;
         for (i=0;i<lista[x].size();i++)
         {
              z=d[x]+lista[x][i].cost;
              if (z<d[lista[x][i].vf])
              {
                   d[lista[x][i].vf]=z;
                   up[lista[x][i].vf]++;
                   if (in[lista[x][i].vf]==0)
                   {
                        in[lista[x][i].vf]=1;
                        coada.push(lista[x][i].vf);
                   }
                   if (up[lista[x][i].vf]==n)
                    {
                         ciclu=1;
                         break;
                    }
              }
         }
    }
    if (ciclu)
          fout<<"Ciclu negativ!"<<'\n';
     else
     {
          for (i=2;i<=n;i++)
               fout<<d[i]<<' ';
          fout<<'\n';
     }
     fout.close();
     return 0;
}