#include <iostream>
#include <fstream>
#define maxn 50010
#define maxm 250010
#define inf 1000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct l_muchii
{
    int x,y,c;
}mm[maxm];

long i,j,n,m,cost[maxn];

void read_ini()
{
    f>>n;
    f>>m;
    for(i=0; i<m ;i++)
    {
        f>>mm[i].x;
        f>>mm[i].y;
        f>>mm[i].c;
    }
    cost[1]=0;
    for(i=2; i<=n ;i++)
        cost[i]=inf;
}

void bellman()
{
    int ok;
    for(i=ok=1; i<n && ok;i++)
    {
        for(j=ok=0; j<m ;j++)
        {
            if(cost[mm[j].x] + mm[j].c < cost[mm[j].y])
            {
                cost[mm[j].y] = cost[mm[j].x] + mm[j].c;
                ok=1;
            }
        }
    }
}

int ciclu_negativ()
{
    for(i=0; i<m; i++)
        if(cost[mm[i].x]+mm[i].c<cost[mm[i].y])
            return 1;
    return 0;
}


int main()
{
    read_ini();
    bellman();
    if(ciclu_negativ())
    {
        g<<"Ciclu negativ!\n";
    }
    else
    {
        for(i=1; i<=n ;i++)
            g<<cost[i]<<" ";
    }
    return 0;
}