#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<vector<pair<int, int>>> graf;
vector<int> tata;
vector<int> d;
vector<int> inq;
vector<int> contor;
queue<int> q;

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

void bellmanford(bool& ok)
{
    d[1] = 0;
    q.push(1);
    inq[1] = 1;

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        inq[nod] = 0;

        for(auto& vec : graf[nod])
        if(d[vec.first] > d[nod] + vec.second)
        {
            d[vec.first] = d[nod] + vec.second;
            tata[vec.first] = nod;

            contor[vec.first]++;
            if(contor[vec.first >= N])
            {
                ok = 1;
                return;
            }

            if(inq[vec.first] == 0)
                {
                    q.push(vec.first);
                    inq[vec.first] = 1;
                }

        }
    }

}

int main()
{

    fin>>N>>M;
    graf.resize(N+1);
    tata.assign(N+1, 0);
    d.assign(N+1, inf);
    inq.assign(N+1, 0);
    contor.assign(N+1, 0);
    for(int i=1; i<=M; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        graf[x].push_back({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;
}