#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;
};

vector<edge> G[NMAX];
queue<int> q;
bool inQ[NMAX];
int dist[NMAX];
int nrQ[NMAX];
int n;

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

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);
    ++nrQ[start];
    inQ[start] = true;

    bool negativeCycle = false;
    while(!q.empty() && !negativeCycle) {
        int nod = q.front();
        q.pop();
        inQ[nod] = false;

        for(auto neigh:G[nod]) {
            if(dist[neigh.nod] > dist[nod] + neigh.cost) {
                dist[neigh.nod] = dist[nod] + neigh.cost;
                if(!inQ[neigh.nod]) {
                    q.push(neigh.nod);
                    inQ[neigh.nod] = true;
                    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;
}