#include<bits/stdc++.h>
using namespace std;
#define in f
#define out g

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

int const MAXSIZE = 50010;
int const INF = 2000000000;
int n, m;
int x, y, z;
int dist[MAXSIZE];

struct edge{
    int x;
    int y;
    int cost;
};

vector <edge> edges;

int bellmanford() {
    for (int j = 1; j < n; j++) {
        for (int k = 0; k < edges.size(); k++) {
            if (dist[edges[k].x] + edges[k].cost < dist[edges[k].y])
                dist[edges[k].y] = dist[edges[k].x] + edges[k].cost;
        }
    }
}

int cycle() {
    for (int k = 0; k < edges.size(); k++) {
        if (dist[edges[k].x] + edges[k].cost < dist[edges[k].y])
            return 1;
    }
    return 0;
}


int main() {

    in >> n >> m;

    for(int i = 1; i <= m; i++) {
        in >> x >> y >> z;
        edge e;
        e.x = x;
        e.y = y;
        e.cost = z;
        edges.push_back(e);
    }

    for (int i = 2; i <= n; i++)
        dist[i] = INF;
    bellmanford();
    if (cycle()) {
        out <<  "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; i++) {
            out << dist[i] << " ";
        }
    }
}