#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

typedef unsigned long long ull;


void getint(int& x) {
    char c;
    while (cin.get(c) && !cin.eof() && isspace(c));
    if (cin.eof()) return;
    x = c - '0';
    while (cin.get(c) && !cin.eof() && isdigit(c)) x = x * 10 + (c - '0');
}


const int sze = 5e4;
const int oo = 1e4;
int n, m;
class vec {
public:
    int nod1, nod2, cost;
};
vector<vec> v;
int D[sze + 1];
bool BellmanFord(int st) {
    for (int i = 1; i <= n; ++i) D[i] = oo;
    D[st] = 0;
    bool ok = true;
    for (int i = 1; i < n && ok; ++i) {
        ok = false;
        for (auto k : v) {
            if (D[k.nod2] > D[k.nod1] + k.cost) {
                D[k.nod2] = D[k.nod1] + k.cost;
                ok = true;
            }
        }
    }
    for (auto k : v) {
        if (D[k.nod2] > D[k.nod1] + k.cost) {
            return true;
        }
    }
    return false;
}


int main() {
    getint(n);
    getint(m);
    int a, b, c;
    while (m--) {
        getint(a);
        getint(b);
        getint(c);
        v.push_back({ a, b, c });
    }
    sort(v.begin(), v.end(), [](vec a, vec b) { return a.nod1 < b.nod1; });

    if (BellmanFord(1)) cout << "Ciclu negativ!";
    else {
        for (int i = 2; i <= n; ++i) cout << D[i] << " ";
    }



    
    return 0;
}