#include <iostream>
#include <fstream>
#define INF 999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
int inc,sf;
struct nod
{
    int vecin;
    int val;
    struct nod *urm;
}*L[50005],*actual;
int d[50005];
int viz[50005];
int c[2000000];
bool bellmanford(int k)
{
    while(inc<=sf)
    {
        actual=L[c[inc]];
        while(actual!=NULL)
        {
            if(actual->val+d[c[inc]]<d[actual->vecin]&&d[c[inc]]!=INF&&viz[actual->vecin]!=n-1)
            {
                sf++;
                c[sf]=actual->vecin;
                d[actual->vecin]=actual->val+d[c[inc]];
                viz[actual->vecin]++;
                if(viz[actual->vecin]==n-1)
                    return 0;
            }
            actual=actual->urm;
        }
        inc++;
    }
    return 1;
}
int main()
{
    int i,x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        actual=new nod;
        actual->vecin=y;
        actual->urm=L[x];
        actual->val=z;
        L[x]=actual;
    }
    for(i=2;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    inc=sf=1;
    c[sf]=1;
  /*  while(inc<=sf)
    {
        for(i=1;i<=m;i++)
        {
            if(c[inc]==v[i].x)
            {
                if(d[v[i].x]+v[i].cost<d[v[i].y]&&d[v[i].x]!=INF&&viz[v[i].y]==false)
                {
                    d[v[i].y]=v[i].cost+d[v[i].x];
                    viz[v[i].y]++;
                    c[sf]=v[i].y;
                    sf++;
                }
            }
        }
        if(viz[v[i].y]==n-1){
            ok=1;
            break ;
        }
        viz[c[inc]]=false;
        inc++;
    }
    if(ok==0)
    {
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    else
        g<<"Ciclu negativ";
    */
    bool ok=bellmanford(1);
    if(ok==1)
    {
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    else
        g<<"Ciclu negativ!";
    return 0;
}