#include <bits/stdc++.h>
#define NMAX 50005
#define INF 999999999

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<vector<pair<int, int>>> gr;
int n, m;
int x, y, c;
int distanta[NMAX];

void read() {
    fin >> n >> m;
    gr.resize(n + 1);
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        gr[x].push_back({y, c});
    }
}

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

vector<int> bellman_ford(int source) {
    setDistances();
    distanta[source] = 0;

    for (int i = 0; i < n; ++i) {
        for (int x = 1; x <= n; ++x) {
            for (const auto& vecin : gr[x]) {
                int v = vecin.first;
                int cost = vecin.second;
                if (distanta[x] != INF && distanta[x] + cost < distanta[v]) {
                    if (i == n - 1) return {-1};
                    distanta[v] = distanta[x] + cost;
                }
            }
        }
    }

    return vector<int>(distanta + 1, distanta + n + 1);
}

int main() {
    read();
    vector<int> result = bellman_ford(1);

    if (result[0] == -1) {
        fout << "Ciclu negativ!\n"; // Negative cycle detected
    } else {
        for (int i = 2; i <= n; ++i) {
            fout << distanta[i] << ' ';
        }
        fout << "\n";
    }

    return 0;
}