#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 50000
#define MMAX 250000

#define INF 0x3f3f3f3f

struct edge
{
    int u, v, w;
};

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

    bool used[NMAX];
    int n, m, d[NMAX], cnt[NMAX];
    std::vector<edge> g[NMAX];
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        edge ed;
        scanf("%d %d %d", &ed.u, &ed.v, &ed.w);
        ed.u--; ed.v--;
        g[ed.u].push_back(ed);
    }

    for(int i = 0; i < n; i++)
    {
        d[i] = INF;
        used[i] = false;
        cnt[i] = 0;
    }
    
    bool cycle = false;
    std::queue<int> Q;
    Q.push(0);
    d[0] = 0;
    used[0] = true;
    while(!Q.empty() && !cycle)
    {
        int u = Q.front();
        Q.pop();
        used[u] = false;
        for(const edge& e : g[u])
            if(d[u] + e.w < d[e.v])
            {
                d[e.v] = d[u] + e.w;
                if(!used[e.v])
                {
                    Q.push(e.v);
                    used[e.v] = true;
                    cnt[e.v]++;
                    if(cnt[e.v] > n)
                        cycle = true;
                }
            }
    }

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