#include <bits/stdc++.h>

using namespace std;

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

//Bellman Ford

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

int n,m;
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
    vector <int> dist(50002, 1000000000);
    dist[1]=0;
    //Loop
    bool changed=true;
    while (changed)
    {
        ++cont;
        if (cont==n)
            break;
        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])
                {
                    /*for (int i=1;i<=n;i++)
                        cout << dist[i] << " ";
                    cout << "\n";*/
                    dist[j]=dist[i]+c;
                    changed=true;
                }
            }

    }
    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 << " ";
        }
}

void afisare()
{
    /*for (int i=1;i<=n;i++)
            cout << pre[i] << " ";
        cout << "\n";*/

}

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