#include <stdio.h>

#include <vector>
#include <queue>

#define INF 1000000

struct edge {
    edge()
    {
        u = v = w = 0;
    }
    edge(int _u, int _v, int _w)
    {
        u = _u;
        v = _v;
        w = _w;
    }

    bool operator<(const edge& e) const
    {
        return e.w < w;
    }

    int u, v, w;
};

edge edges[250000];
int distances[50000];

int bellman_ford(int n, int m)
{
    for (int i = 1; i < (n - 1); i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;
            if ((distances[u] + w) < distances[v]) 
                distances[v] = distances[u] + w;
        }
    }

    for (int i = 1; i < (n - 1); i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;
            if ((distances[u] + w) < distances[v])
                return 1;
        }
    }

    return 0;
}

int main()
{
    int n, m;

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    scanf("%d %d\n", &n, &m);

    for (int i = 0; i < n; i++) 
        distances[i] = INF;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d\n", &u, &v, &w);

        edges[i] = edge(u - 1, v - 1, w);
    }

    distances[0] = 0;

    if (bellman_ford(n, m)) 
        printf("Ciclu negativ!\n");
    else {
        for (int i = 1; i < n; i++) 
            printf("%d ", distances[i]);
        printf("\n");
    }

    return 0;
}