#include <fstream>
#include <vector>

using namespace std;

const int MMAX = 250005;
const int INF = 2e9;

int n,m;
vector<int> dist;

struct graf {
    int from, to, cost;
};

graf graph[MMAX];

bool bellman() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int u = graph[j].from;
            int v = graph[j].to;
            int cost = graph[j].cost;
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int u = graph[i].from;
        int v = graph[i].to;
        int cost = graph[i].cost;
        if (dist[u] + cost < dist[v]) {
            return false;
        }
    }

    return true;
}

int main() {

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

    fin >> n >> m;
    dist.resize(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        int x,y,c;
        fin >> x >> y >> c;
        graph[i].from = x;
        graph[i].to = y;
        graph[i].cost = c;
    }

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

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

    fin.close();
    fout.close();
    return 0;
}