#include <fstream>

using namespace std;

const int N=1001, INF=1000000000;
struct grup
{
    int x, y,c;
};

grup g[250000];

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

int n, m, d[1001];

void citire()
{
    int i,x, y, c;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>g[i].x>>g[i].y>>g[i].c;
}

void afisare()
{
    int i;
    for(i=2;i<=n;i++)
        out<<d[i]<<" ";
}

void bf(int x0)
{
    bool ok;
    int i,j;
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[x0]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(d[g[j].x]+g[j].c<d[g[j].y])
                d[g[j].y]=d[g[j].x]+g[j].c;
    ok=true;
    for(i=1;i<=m;i++)
        if(d[g[i].x]+g[i].c<d[g[i].y])
            ok=false;
    if(ok)
        afisare();
    else out<<"Ciclu negativ!";

}

int main()
{
    citire();
    bf(1);
    return 0;
}