#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define INF 1000000000

struct edge
{
    int a, b, c;
};
int n, m;
vector <edge> edges;
vector <int> d;

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        edges.pb({x, y, c});
    }

    d.resize(n + 1, INF);

    d[1] = 0;
    bool any;
    for(int i = 0; i < n; i ++)
    {
        any = 0;
        for(edge x : edges)
        {
            if(d[x.a] < INF)
            {
                if(d[x.b] > d[x.a] + x.c)
                {
                    d[x.b] = d[x.a] + x.c;
                    any = 1;
                }
            }
        }
    }
    if(any)
        cout << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i ++)
            cout << d[i] << " ";
    return 0;
}