#include <fstream>
#include <vector>
#include<queue>
#define NMAX 50004
#define INF 1e9

using namespace std;

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

int n, x0=1,rez;

struct varf {
    int x;
    int c;
};
vector <varf> G[NMAX];///liste de adicaneta  cu costuri
bool uz[NMAX];
int cmin[NMAX];
int pre[NMAX];
int nr[NMAX];///nr[i] numarul de drumuri de cost minim de la x0 la i
queue<int> C;

void citire();
bool bellmanford();
void afisare();

int main()
{
 citire();
 rez=bellmanford();
 afisare();
 return 0;
}

void citire() {
    int i,j,c,m;
    varf aux;
    fin>>n>>m;
    while(fin>>i>>j>>c)
        {
          ///in lista de adicaneta  a lui i trebuie sa  adaug (j,c)
          aux.x=j; aux.c=c;
          G[i].push_back(aux);
        }
    for(i=1;i<=n;i++)
        cmin[i]=INF;
    cmin[x0]=0;
}

bool bellmanford()
///returneaza 0 daca exista circuite de cost negativ, 1 altfel
{
   int x,vf,cost,i;
   ///initializez coada cu varful de start
   C.push(x0);
   nr[x0]=1;
   while(!C.empty())
        {
          x=C.front(); C.pop();
          ///parcurg lista de adaincenta  lui x
          for(i=0;i<G[x].size();i++)
             {
               vf=G[x][i].x; cost=G[x][i].c;
               if(cmin[vf]>cmin[x]+cost)
                 {
                   cmin[vf]=cmin[x]+cost;
                   C.push(vf);
                   nr[vf]++;
                   if(nr[vf]==n) return 0;

                 }
             }
        }
   return 1;
}


void afisare()
{
 if(rez==0) fout<<"Ciclu negativ!";
   else
   for(int i=2;i<=n;i++)
      {
        fout<<cmin[i]<<' ';
      }
}