#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NRMAX 50005
#define INF 100000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct graf{int vf,c;};
int n,m;
bool ok=1;

queue <int> C;
vector <graf> L[NRMAX];
int cmin[NRMAX];
int pred[NRMAX];
int nr[NRMAX];
vector <bool> uz(NRMAX,0);

void citire();
void BLMF();
void afisare();
int main()
{
   citire();
   BLMF();
   afisare();
    return 0;
}

void citire()
{
    int i,v1,v2,c;

    fin>>n>>m;
    for(i=1;i<=m;i++)
        {fin>>v1>>v2>>c;
         L[v1].push_back({v2,c});
        }

for(i=1;i<=n;i++)
    {cmin[i]=INF;
     pred[i]=0;
    }
//for(i=0;i<L[1].size();i++)
  //  cmin[L[1][i].vf]=L[1][i].c;

cmin[1]=0;  uz[1]=1;    nr[1]++;
C.push(1);
}

void BLMF()
{
    int x,i;

    while(!C.empty())
    {
     x=C.front();C.pop();
     uz[x]=0;

     for(i=0;i<L[x].size();i++)
         {
          if(cmin[L[x][i].vf] > cmin[x] + L[x][i].c)
            {
              cmin[L[x][i].vf]=cmin[x] + L[x][i].c;
              pred[L[x][i].vf]=x;
              nr[L[x][i].vf]++;

              if(uz[L[x][i].vf]==0)
              {
                 C.push(L[x][i].vf);
                 uz[L[x][i].vf]=1;
                 if(nr[L[x][i].vf]>n)
                 {
                     ok=0;
                     return;
                 }
              }
            }
         }
    }



}

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

    fout<<'\n';
}