#include <bits/stdc++.h>

using namespace std;

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

//Dijkstra = Greedy

vector<vector<pair<int,int> > > v(50002);

int n,m,s=1;
int dist[50002];
int cont;

void citire()
{
    fin >> n >> m;
    int i,j,c;
    while (fin >> i >> j >> c)
        v[i].push_back({j,c});
    /*for (int i=1;i<=n;i++)
        for (auto j:v[i])
            fout << i << " -> " << j.first << " = " << j.second << "\n";
    */
}

void rez()
{
    //Initializare
    for (int i=1;i<=n;i++)
        dist[i]=1e7;
    dist[s]=0;
    //Loop
    bool changed=true;
    while (changed && cont<n)
    {
        ++cont;
        changed=false;
        for (int i=1;i<=n;i++)
            for (auto k:v[i])
            {
                int j=k.first;
                int c=k.second;
                if (dist[i]+c<dist[j])
                {
                    dist[j]=dist[i]+c;
                    changed=true;
                }
            }
    }
    /*for (int i=1;i<=n;i++)
        cout << dist[i] << " ";
    cout << "\n";*/
}

void afisare()
{
    /*for (int i=1;i<=n;i++)
            cout << pre[i] << " ";
        cout << "\n";*/
    if (cont==n)
        fout << "Ciclu negativ!";
    else
        for (int i=2;i<=n;i++)
        {
            if (dist[i]==1e7)
                fout << -1;
            else
                fout << dist[i];
            if (i<n)
                fout << " ";
        }
}

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