#include <iostream>
#include<fstream>
using namespace std;
#define MX 99999999
int d[50001],i,j,n,m,k,w,x,y;
bool ok;
struct
{
    int x,y,d;
}v[250001];
int main()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>v[i].x>>v[i].y>>v[i].d;

    }
    for(i=1;i<n;++i)d[i+1]=MX;
    for(j=0;j<n;++j)
    {
        for(i=0;i<m;++i)
        {
            w=v[i].d;x=v[i].x;y=v[i].y;
            if(d[x]+w<d[y])d[y]=d[x]+w;
        }
    }
    ok=0;
    for(i=0;i<m&&ok<1;++i)
        {
            w=v[i].d;x=v[i].x;y=v[i].y;
            if(d[x]+w<d[y])ok=1;
        }
    ofstream g("bellmanford.out");
    if(ok>0)g<<"Ciclu negativ!";
    else
        for(i=1;i<n;++i)g<<d[i+1]<<" ";
    g.close();
    return 0;
}