#include <bits/stdc++.h>
using namespace std;

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

struct Nod
{
    int nod, cost;
};

const int Nmax =  50005;
const int INF = (1 << 30);

vector < Nod > L[Nmax];
queue < int > Q;
int n, m;
int dist[Nmax];
int freq[Nmax];
bool viz[Nmax];

int main()
{
    int x, y, c, i;
    bool cycle = false;

    fin >> n >> m;
    for(i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y , c});
    }

    for(i = 1 ; i <= n ; i++)
        dist[i] = INF;

    dist[1] = 0;
    viz[1]  = true;
    freq[1] = 1;

    Q.push(1);
    while(! Q.empty() && !cycle)
    {
        x = Q.front();
        Q.pop();

        viz[x] = false;
        for(auto w : L[x])
            if(dist[w.nod] > dist[x] + w.cost)
            {
                dist[w.nod] = dist[x] + w.cost;
                if(!viz[w.nod])
                {
                    viz[w.nod] = true;
                    ++freq[w.nod];
                    if(freq[w.nod] > n)
                        cycle = true;
                    Q.push(w.nod);
                }
            }
    }

    if(cycle)
        fout << "Ciclu negativ!\n";
    else
    {
        for(i = 2; i <= n; i++)
            fout << dist[i] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}