#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 citire() {
    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)
void bellmanford() {
    int dist[n+1];

    for (int i = 1; i <= n; i++)
        dist[i] = inf;

    dist[1] = 0;

    queue<int> q;
    bool inq[n+1] = {};

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

    int cnt[n+1] = {};

    bool neg = false;

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

        inq[nod] = false;

        for (auto e : edges) {
            int p1, p2, c;
            tie(p1, p2, c) = e;

            if (p1 == nod && dist[p1] + c < dist[p2]) {
                dist[p2] = dist[p1] + c;

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

                    cnt[p2]++;

                    if (cnt[p2] >= 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;
}