#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));
 
    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 : l[nod])
        {
            if (dist[nod] + next.w < dist[next.to])
            {
                dist[next.to] = dist[nod] +  next.w;
 
                if (!inq[next.to])
                {
                    inq[next.to] = true;
 
                    cnt[next.to]++;
 
                    if (cnt[next.to] > n)
                    {
                        cicluNegativ = true;
                    }
                    q.push(next.to);
                }
            }
        }
    }
 
    return cicluNegativ;
}

int main()
{
    fin >> n >> m;
 
    for (int i = 1; i <= m; i++)
    {
        int f, t, w;
 
        fin >> f >> t >> w;
 
        l[f].push_back({t, w});
    }
 
 
    if (BellMan())
    {
        fout << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            fout << dist[i] << ' ';
        }
    }
    

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