#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie
{
    int n1, n2, c;
};

vector<muchie> graf;
vector<int> tata;
vector<int> d;

int N, M;
const int inf = 1e9;

void bellmanford(bool& ok)
{
    d[1] = 0;
    for(int k=1; k<=N-1; k++)
    {
        for(auto& muc : graf)
            if(d[muc.n2] > d[muc.n1] + muc.c)
            {
                d[muc.n2] = d[muc.n1] + muc.c;
                tata[muc.n2] = muc.n1;
            }
    }
    for(auto& muc : graf)
        if(d[muc.n2] > d[muc.n1] + muc.c)
            ok = 1;
}

int main()
{

    fin>>N>>M;
    tata.assign(N+1, 0);
    d.assign(N+1, inf);
    for(int i=1; i<=M; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        graf.push_back({x, y, c});
    }

    bool ok = 0;

    bellmanford(ok);

    if(ok == 1)
    {
        fout<<"Ciclu negativ!";
    }
    else if(ok == 0)
    {
        for(int i=2; i<=N; i++)
            fout<<d[i]<<' ';
    }

    return 0;
}