#include <iostream>
#include <fstream>

using namespace std;

#define infinit 100000000;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n,m,*cost,i,j;
    struct M
    {
        int a,b,c;
    }muchie[100];
    f>>n;
    cost=new int [n+1];
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>muchie[i].a;
        f>>muchie[i].b;
        f>>muchie[i].c;
    }
    cost[1]=0;
    for (i=2;i<=n;i++)
        cost[i]=1000000;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            if (cost[muchie[j].a]+muchie[j].c<cost[muchie[j].b])
                cost[muchie[j].b]=cost[muchie[j].a]+muchie[j].c;
    }
    int ok=1;
    for (i=1;i<=m;i++)
        if (cost[muchie[i].a]+muchie[i].c<cost[muchie[i].b])
            ok=0;
    if (ok)
        for (i=1;i<=n;i++)
            cout<<cost[i]<<" ";
    else
        cout<<"Ciclu negativ";
    return 0;
}