#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

typedef struct ls
{
    int info, drum;
    ls *next;
}*nod;

int c, y, u, i, j, x, n, m, f[500005], sol[50005];
nod a[50005];
int viz[50005];

void ad(int x, nod &y, int c)
{
    nod p=new ls;
    p->info=x;
    p->drum=c;
    p->next=y;
    y=p;
}


int main()
{
    cin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        cin>>x>>y>>c;
        ad(y, a[x], c);
    }


    for (i=2; i<=n; ++i) sol[i]=20000;
    u=0; sol[1]=0;
    y=1; f[1]=1;


    for(i=1; i<=y; ++i)
    {
        for (nod p=a[f[i]]; p; p=p->next)

            if (sol[f[i]]+p->drum < sol[p->info])
            {
                sol[p->info]=sol[f[i]]+p->drum;
                ++viz[p->info];
                f[++y]=p->info;
                if (viz[p->info]==n)
                {
                    u=1;
                    i=y+2;
                }
            }
    }
    if (u) cout<<"Ciclu negativ!\n";
    else
    for (i=2; i<=n; ++i) cout<<sol[i]<<' ';


    return 0;
}