#include <cstdio>
#include <vector>

using namespace std;

struct edge {int v1; int v2; int cost;};

vector<edge> edges;
int d[50002];
int n;
const int INF = 1000000;

bool bellmanford(int source)
{
    for (int i = 1; i <= n; ++i)
        if (i != source)
            d[i] = INF;

    int v1, v2, cost;
    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j < edges.size(); ++j)
        {
            v1 = edges[j].v1;
            v2 = edges[j].v2;
            cost = edges[j].cost;
            if (d[v1] + cost < d[v2])
                d[v2] = d[v1] + cost;
        }
    }

    for (int j = 0; j < edges.size(); ++j)
    {
        v1 = edges[j].v1;
        v2 = edges[j].v2;
        cost = edges[j].cost;
        if (d[v1] + cost < d[v2])
            return 0;
    }
    return 1;
}

int main()
{
    FILE *in = fopen("bellmanford.in", "r");
    FILE *out = fopen("bellmanford.out", "w");

    int m;
    fscanf(in, "%d%d", &n, &m);

    for (int x, y, c; m >= 0; --m)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        edge t;
        t.v1 = x;
        t.v2 = y;
        t.cost = c;
        edges.push_back(t);
    }

    if (bellmanford(1))
    {
        fprintf(out, "%d", d[2]);
        for (int i = 3; i <= n; ++i)
            fprintf(out, " %d", d[i]);
        fprintf(out, "\n");
    }
    else
        fprintf(out, "Ciclu negativ!\n");

    fclose(in);
    fclose(out);

    return 0;
}