#include <bits/stdc++.h>

using namespace std;

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

const unsigned nmax = 100005;

struct edge{
    int i;
    int j;
    int cost;
    edge(int _i, int _j, int _cost): i(_i), j(_j), cost(_cost) {}
};
int main()
{
    int N, M;
    fin >> N >> M;
    vector<edge> edges;
    int distMin[nmax];
    distMin[1] = 0;
    for(int i = 2; i <= N; ++i)
        distMin[i] = INT_MAX / 2;
    for(int i = 1; i <= M; ++i)
    {
        int c, x, y;
        fin >> c >> x >> y;
        edges.push_back(edge(c, x, y));
    }
    bool ok;
    for(int i = 0; i < N; ++i){
        ok = false;
        for(auto edge: edges)
            {
                int temp = distMin[edge.j];
                distMin[edge.j] = min(distMin[edge.j], distMin[edge.i] + edge.cost);
                if (distMin[edge.j] != distMin[edge.j])
                    ok = true;
            }
        if(ok == false) break;
    }
    for(int i = 0; i < M; ++i)
    {
        int ii = edges[i].i;
        int j = edges[i].j;
        int cost = edges[i].cost;
        if(distMin[ii] + cost < distMin[j])
            {
                fout << "Ciclu negativ!";
                return 0;
            }
    }
    for(int i = 2; i <= N; ++i)
        fout << distMin[i] << ' ';
    return 0;
}