#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;
int dist[50002];

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=2;i<=n;i++)
        dist[i]=1000000000;
    //Loop
    while (true)
    {
        bool changed=true;
        ++cont;
        if (cont==n)
            break;
        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=false;
                }
            }
        if (changed)
            break;
    }
    if (cont==n)
        fout << "Ciclu negativ!";
    else
        for (int i=2;i<=n;i++)
        {
            fout << dist[i];
            if (i<n)
                fout << " ";
        }
}

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