#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 = INT_MAX;
int n, m;
class vec {
public:
    int nod, cost;
};
vector<vec> G[sze + 1];
int D[sze + 1];
int F[sze + 1];
class compare {
public:
    bool operator()(int a, int b) {
        return D[a] > D[b];
    }
};
bool BellmanFord() {
    for (int i = 2; i <= n; ++i) D[i] = oo;
    priority_queue<int, vector<int>, compare> q;
    q.push(1);
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        F[t]++;
        if (F[t] == n) return true;
        for (auto k : G[t]) {
            if (D[k.nod] > D[t] + k.cost) {
                D[k.nod] = D[t] + k.cost;
                q.push(k.nod);
            }
        }
    }
    return false;
}


int main() {
    cin >> n >> m;
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        G[a].push_back({ b, c });
    }

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



    
    return 0;
}