#include <bits/stdc++.h>
using namespace std;

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

int n, m;

vector<Edge>edges;
vector<int>dist;

int main()
{
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
scanf("%d %d",&n, &m);
dist.assign(n+1, INT_MAX);
edges.resize(m);
for(int i = 0; i < m; i++)
{
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    edges[i].u = x; edges[i].v = y; edges[i].w = c;
}

dist[1] = 0;
for(int i = 1; i <= n-1; i++)
{
    bool changed = false;
    for(const auto& e : edges)
    {
        if(dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
        {
            dist[e.v] = dist[e.u] + e.w;
            changed = true;
        }
    }
    if(!changed) break;
}

bool ciclu_negativ = false;
for(const auto& e : edges)
{
    if(dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
        ciclu_negativ = true;
}

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

    return 0;
}