#include <fstream>
#include <climits>

#define NMAX 50005
#define MMAX 250005

using namespace std;

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

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

int n, m;
int answer[NMAX];
Edge edge[MMAX];

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> edge[i].x >> edge[i].y >> edge[i].cost;
    }

    for (int i = 2; i <= n; i++)
        answer[i] = INT_MAX;

    for (int i = 1; i < n; i++) {

        for (int j = 1; j <= m; j++) {
            int x = edge[j].x;
            int y = edge[j].y;
            int cost = edge[j].cost;

            if (answer[x] != INT_MAX && answer[x] + cost < answer[y])
                answer[y] = answer[x] + cost;
        }
    }

    for (int i = 1; i <= m; i++) {
        int x = edge[i].x;
        int y = edge[i].y;
        int cost = edge[i].cost;

        if (answer[x] != INT_MAX && answer[x] + cost < answer[y]) {
            g << "Ciclur negativ!";
            return 0;
        }
    }

    for (int i = 2; i <= n; i++)
        g << answer[i] << " ";
    g << "\n";

    return 0;
}