#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define Nmax 50009
#define oo (1<<31)

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

typedef pair<int,int> edge;
#define neighbour first
#define cost second

int n,m,x,y,c,used[Nmax],d[Nmax];
vector <edge> G[Nmax];
queue <int> Q;

void ReadInput() {

    f>>n>>m;
    for (int i=1; i<=m; ++i) {

        f>>x>>y>>c;
        G[x].push_back( edge(y,c) );
    }
}

bool BellmanFord(int source) {

    for (int i=1; i<=n; ++i) d[i]=oo;

    Q.push(source);
    d[source]=0;

    while (!Q.empty()) {

        int node = Q.front();
        Q.pop();

        ++used[node];

        if (used[node] == n) return true;

        for (auto it: G[node]) {

            x = it.neighbour;
            c = it.cost;

            if ((d[x] >= d[node]+c) || d[x]==oo) {

                d[x] = d[node]+c;
                Q.push(x);
            }
        }
    }

    return false;
}

void Solve() {

    if (BellmanFord(1)) g<<"Ciclu negativ!";
    else {

        for (int i=2; i<=n; ++i) {

            if (d[i]==oo) g<<0<<' ';
            else g<<d[i]<<' ';
        }
    }
}

int main() {

    ReadInput();
    Solve();

    f.close(); g.close();
    return 0;
}