#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;
vector<int> inq;
queue<int> q;

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

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

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

        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;
            if(inq[muc.n2] == 0)
                q.push(muc.n2);

        }
    }
    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);
    inq.assign(N+1, 0);
    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;
}