#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 5e4;
const int INF = 25e7 + 1;

struct arc{
    int vf, c;
};

vector <arc> suc[NMAX + 1];
int d[NMAX + 1];

void iss(int s, int n){
    for(int i = 1; i <= n; i++){
        d[i] = INF;
    }
    d[s] = 0;
}

void relax(int ns, int nd, int c){
    d[nd] = min(d[nd], d[ns] + c);
}

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

    int n, m;
    fin >> n >> m;

    for(int i = 0; i < m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        suc[x].push_back((arc){y, c});
    }

    iss(1, n);

    for(int i = 1; i < n; i++){
        for(int x = 1; x <= n; x++){
            for(auto y: suc[x]){
                relax(x, y.vf, y.c);
            }
        }
    }

    bool are_cn = false;
    for(int x = 1; x <= n && !are_cn; x++){
        for(auto y: suc[x]){
            int ns = x;
            int nd = y.vf;
            int c = y.c;
            if(d[nd] > d[ns] + c){
                are_cn = true;
                break;
            }
        }
    }

    if(are_cn){
        fout << "Ciclu negativ!";
    }else{
        for(int i = 2; i <= n; i++){
            fout << d[i] << " ";
        }
    }


    fin.close();
    fout.close();
    return 0;
}