#include <fstream>
using namespace std;

#define NMax 50001
#define MMax 250001
#define inf 2100000000

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct muchie{int x,y,val;};

int n,m;
muchie lista[MMax];
int drum[NMax];

void init()
{
    int i;
    drum[1]=0;
    for(i=2;i<=n;i++) drum[i]=inf;
}

void bellmanford()
{
    int i,j;
    for(j=1;j<n;j++)
        for(i=1;i<=m;i++)
            if(drum[ lista[i].y ]>drum[ lista[i].x ]+lista[i].val)
                drum[ lista[i].y ]=drum[ lista[i].x ]+lista[i].val;
}

int ciclu()
{
    int i;
    for(i=1;i<=m;i++) if(drum[ lista[i].y ]>drum[ lista[i].x ]+lista[i].val) return 0;
    return 1;
}

int main()
{
    int i,ok;

    f>>n>>m;
    for(i=1;i<=m;i++) f>>lista[i].x>>lista[i].y>>lista[i].val;

    init();
    bellmanford();
    ok=ciclu();

    if(ok==1) for(i=2;i<=n;i++) g<<drum[i]<<" ";
    else g<<"Ciclu negativ!";
    g<<"\n";

    f.close();
    g.close();
    return 0;
}