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

using namespace std;

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

const int nMax = 50000 + 10;

struct Node
{
    int to, w;
};

int n, m;

int dist[nMax], cnt[nMax];
vector < Node > l[nMax];

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

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

bitset < nMax > inq;

bool BellMan()
{
    bool cicluNegativ = false;

    memset(dist, 5, sizeof(dist));
    
    dist[1] = 0;
    inq[1] = 1;
    cnt[1] = 1;
    q.push(1);

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

        inq[node] = 0;

        for (Node next : l[node])
        {
            if (dist[node] + next.w < dist[next.to])
            {
                dist[next.to] = dist[node] + next.w;

                if (!inq[next.to])
                {
                    inq[next.to] = 1;
                    q.push(next.to);

                    cnt[next.to]++;

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

    return cicluNegativ;
}

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

    for (int i = 1; i <= m; i++)
    {
        int a, b, w;

        fin >> a >> b >> w;

        l[a].push_back({b, w});
    }


    if (BellMan())
    {
        for (int i = 2; i <= n; i++)
        {
            fout << dist[i] << ' ';
        }


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

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