#include <iostream>
#include <fstream>
#define INF 999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
struct muchie
{
    int x;
    int y;
    int cost;
}v[250002];
int d[50005];
int viz[50005];
int c[2000000];
int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    for(i=2;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    int inc,sf;
    inc=sf=1;
    c[sf]=1;
    sf++;
    bool ok=0;
    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";
    */
    if(ok==0)
    {
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    else
        g<<"Ciclu negativ";
    return 0;
}