#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;

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() {
    cin >> n >> m;
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        v.push_back({ a, b, c });
    }

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



    
    return 0;
}