#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nMax = 50000 + 5;


bitset < nMax > inq;
int dist[nMax], cnt[nMax];
int n, m;

struct Node
{
    int next, w;
};

vector < Node > g[nMax];

struct Comp
{
    bool operator() (int a, int b)
    {
        return dist[a] > dist[b];
    }
};

priority_queue<int, vector < int >, Comp > q;

bool Dijkstra()
{
    bool cicluNegativ = false;

    memset(dist, 5, sizeof(dist));

    q.push(1);
    inq[1] = true;
    cnt[1] = 1;
    dist[1] = 0;

    while (!q.empty() && !cicluNegativ)
    {
        int nod = q.top();
        q.pop();

        inq[nod] = false;

        for (Node next : g[nod])
        {
            if (dist[nod] + next.w < dist[next.next])
            {
                dist[next.next] = dist[nod] +  next.w;

                if (!inq[next.next])
                {
                    inq[next.next] = true;

                    cnt[next.next]++;

                    if (cnt[next.next] > n)
                    {
                        cicluNegativ = true;
                    }
                    q.push(next.next);
                }
            }
        }
    }

    return cicluNegativ;
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int f, t, w;

        fin >> f >> t >> w;

        g[f].push_back({t, w});
    }


    if (Dijkstra())
    {
        fout << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            fout << dist[i] << ' ';
        }
    }
    

    fin.close();
    fout.close();
    return 0;
}