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

using namespace std;

const int NMAX = 250002, INF = 0x3f3f3f3f;

vector <pair<int, int> > v[NMAX];
queue <int> q;
vector<int> sol;

int d[NMAX], seen[NMAX], inq[NMAX], m, n;

int main() {
    ifstream cin ("bellmanford.in");
    ofstream cout ("bellmanford.out");
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y, c;

        cin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }

    q.push(1);

    for (int i = 1; i <= n; i++) {
        d[i] = INF;
    }

    d[1] = 0;
    seen[1] = 1;

    while(!q.empty()) {
        int nod = q.front();

        q.pop();
        inq[nod] = 0;

        for (int i = 0; i < v[nod].size(); i++) {
            pair<int, int> dest = v[nod][i];
            
            if (d[dest.first] > d[nod] + dest.second) {
                d[dest.first] = d[nod] + dest.second;

                seen[dest.first]++;

                if (seen[dest.first] == n - 1) {
                    cout << "Ciclu negativ!";

                    return 0;
                }

                if (!inq[dest.first]) {
                    q.push(dest.first);
                    inq[dest.first] = 1;
                }
            }
        }
    }

    int cmin = INF, pmin;

    for (int i = 2; i <= n; i++) {
        cout << d[i] << " ";
    }

    return 0;
 }