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

using namespace std;

#ifdef INFOARENA
#define cout fout
#endif // INFOARENA

#define NMAX 50010
#define INF 0x3f3f3f3f

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

struct edge {
    int nod, cost;

    bool operator < (const edge& other) const {
        return cost > other.cost;
    }
};

vector<edge> G[NMAX];
priority_queue<edge> q;
int dist[NMAX];
int nrQ[NMAX];
int n;

void init()
{
    memset(dist, INF, sizeof dist);
}

void read()
{
    int m,x,y,cost;
    fin>>n>>m;
    for(; m; --m) {
        fin>>x>>y>>cost;
        G[x].push_back({y,cost});
    }
}

bool bellmanFord(int start)
{
    dist[start] = 0;
    q.push({start, 0});
    ++nrQ[start];

    bool negativeCycle = false;
    while(!q.empty() && !negativeCycle) {
        int nod = q.top().nod;
        q.pop();

        for(auto neigh:G[nod]) {
            if(dist[neigh.nod] > dist[nod] + neigh.cost) {
                dist[neigh.nod] = dist[nod] + neigh.cost;
                q.push({neigh.nod, dist[neigh.nod]});
                if(++nrQ[neigh.nod] >= n) negativeCycle = true;
            }
        }
    }

    return negativeCycle;
}

int main()
{
    init();
    read();
    bool cycle = bellmanFord(1);
    if(cycle) {
        cout<<"Ciclu negativ!";
    } else {
        for(int i = 2; i <= n; ++i)
            cout<<dist[i]<<' ';
    }
    return 0;
}