#include <fstream>
#include <vector>
#include <queue> //coada
#define INF 1000000000
#define NMAX 50010

using namespace std;

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

struct muchie {int y, c;}; //varf si cost

vector <muchie> G[NMAX]; //un vector in care retinem graful
queue <int> q; //coada de tipul int
int dmin[NMAX];
int gr[NMAX];
int nr[NMAX];

int n, m, rez;

void citire();
int bellmanford();
void afisare();

int main()
{
    citire();
    rez=bellmanford();
    afisare();
    return 0;
}

void citire()
{
    int i, x;
    muchie a;
    fin>>n>>m;
    a.y=a.c=0;
    for (i=1; i<=n+1; i++)
        dmin[i] = INF;
    dmin[1]=0;
    for (i=1; i<=m; i++)
        {
        fin>>x>>a.y>>a.c;
        G[x].push_back(a); gr[x]++; //aici retinem lungimea
        }
    q.push(1); //punem varful 1 in coada
}

int bellmanford()
{
    bool cneg=0; //nu avem circuit negativ
    int x, i;
    while (cneg==0&&!q.empty()) //daca nu avem circuit negativ si cat timp coada nu e vida
    {
        x=q.front(); q.pop();
        for (i=0; i<gr[x]; i++)
            if (dmin[G[x][i].y]>dmin[x]+G[x][i].c)
                {
                dmin[G[x][i].y]=dmin[x]+G[x][i].c;
                nr[G[x][i].y]++;
                if (nr[G[x][i].y]==n)
                    {cneg=1; return cneg;}
                q.push(G[x][i].y);
                }
    }
    return cneg;
}

void afisare()
{int i;
    if (rez==1)
        fout<<"Ciclu negativ!"<<'\n';
        else
        {
        for (i=2; i<=n; i++) //varful 1 este varful de start
            fout<<dmin[i]<< ' ';
        fout << '\n';
        }
}