#include <fstream>
#define Infinit 100000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,start,val,ok;
int viz[50001],cmin[50001],tata[50001];
int coada[250001],nrpus[50001];

struct mchie{ int v,cm;
            }c[50001][5001];

void citire();
void init();
void dijkstra();
int bellman_ford(int vf);
void detdrum(int k);
void afisare();

int main()
{
    citire();
    init();
    bellman_ford(1);
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i,x,y,cost,j;
    fin>>n>>m;
    /*for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j) c[i][j]=Infinit;*/

    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x][0].v++;  c[x][c[x][0].v].v=y;
        c[x][0].cm++; c[x][c[x][0].cm].cm=cost;
    }
}

void init()
{
     int i;
     for(i=1;i<=n;i++)
        cmin[i]=Infinit;
}

int bellman_ford(int vf)
{
   int i,j,k,inc=1,sf=1,x;
   cmin[vf]=0; coada[1]=vf;
   while(inc<=sf)
   {
       x=coada[inc++];
       for(i=1;i<=c[x][0].v;i++)
       {
            if(cmin[c[x][i].v]>cmin[x]+c[x][i].cm)
                {
                    coada[++sf]=c[x][i].v;
                    cmin[c[x][i].v]=cmin[x]+c[x][i].cm;
                    nrpus[c[x][i].v]++;
                }
            if(nrpus[c[x][i].v]>=n) {ok=1; break;}
       }
       if(ok) break;
   }
   return ok;
}

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