#include<queue>
#include<fstream>
#include<vector>
#include<tuple>
using namespace std;

// vector<tuple<int,int,int>> edges;
// int n, m;
//
// const int inf = 1e9;
//
// void citire00() {
//     ifstream fin("bellmanford.in");
//
//     fin >> n >> m;
//     edges.resize(m);
//
//     int p1, p2, c;
//
//     for (int i = 0; i < m; i++) {
//         fin >> p1 >> p2 >> c;
//         edges[i] = make_tuple(p1, p2, c);
//     }
// }

/// algoritmul original, dar neoptimizat. pe infoarena da 35p
// void bellmanford() {
//     vector<int> dist(n + 1, inf);
//
//     dist[1] = 0;
//
//     for (int i = 1; i <= n - 1; i++) {
//         for (auto e : edges) {
//             int p1, p2, c;
//             tie(p1, p2, c) = e;
//
//             if (dist[p1] != inf && dist[p1] + c < dist[p2]) {
//                 dist[p2] = dist[p1] + c;
//             }
//         }
//     }
//
//     bool neg = false;
//
//     for (auto e : edges) {
//         int p1, p2, c;
//         tie(p1, p2, c) = e;
//
//         if (dist[p1] != inf && dist[p1] + c < dist[p2]) {
//             neg = true;
//             break;
//         }
//     }
//
//     ofstream fout("bellmanford.out");
//
//     if (neg) {
//         fout << "Ciclu negativ!";
//     }
//     else {
//         for (int i = 2; i <= n; i++) {
//             fout << dist[i] << " ";
//         }
//     }
// }



///alg SPFA ( Shortest Path Faster Algorithm)
vector<vector<pair<int,int>>> adj;
int n, m;

const int inf = 1e9;

void citire() {
    ifstream fin("bellmanford.in");

    fin >> n >> m;

    adj.resize(n + 1);

    int p1, p2, c;

    for (int i = 0; i < m; i++) {
        fin >> p1 >> p2 >> c;
        adj[p1].push_back({p2, c});
    }
}

void bellmanford() {
    vector<int> dist(n + 1, inf);
    vector<bool> inq(n + 1, false);
    vector<int> cnt(n + 1, 0);

    queue<int> q;

    dist[1] = 0;
    q.push(1);
    inq[1] = true;

    bool neg = false;

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

        inq[nod] = false;

        for (auto u : adj[nod]) {
            int vecin = u.first;
            int cost = u.second;

            if (dist[nod] + cost < dist[vecin]) {
                dist[vecin] = dist[nod] + cost;

                if (!inq[vecin]) {
                    q.push(vecin);
                    inq[vecin] = true;

                    cnt[vecin]++;

                    if (cnt[vecin] >= n) {
                        neg = true;
                        break;
                    }
                }
            }
        }

        if (neg)
            break;
    }

    ofstream fout("bellmanford.out");

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

int main() {
    citire();
    bellmanford();

    return 0;
}