#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

#define FILEIN "bellmanford.in"
#define FILEOUT "bellmanford.out"

const int MAXN = 50005;

struct edge {
    int src, dest;
    short weight;

    edge(int src, int dest, int weight) {
        this->src = src;
        this->dest = dest;
        this->weight = weight;
    }
};

int N, M;
vector<edge> G;
int dist[MAXN];

void ReadData() {
    ifstream fin(FILEIN);
    fin >> N >> M;
    for (int i = 0; i < N; i++) {
        int x, y, z;

        fin >> x >> y >> z;
        edge e = edge(x, y, z);
        G.push_back(e);
    }
    fin.close();
}

int Solve() {
    for (int i = 2; i <= N; i++)
        dist[i] = INT_MAX;
    dist[1] = 0;

    for (int i = 2; i <= N; i++) {
        for (edge e : G) {
            int u = e.src;
            int v = e.dest;
            int weight = e.weight;

            if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    for (edge e : G) {
        int u = e.src;
        int v = e.dest;
        int weight = e.weight;
        if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
            return 0;
        }
    }

    return 1;
}

void WriteData(int q) {
    ofstream fout(FILEOUT);

    if (q)
        for (int i = 2; i <= N; i++)
            fout << (dist[i] != INT_MAX ? dist[i] : 0) << ' ';
    else
        fout << "Ciclu negativ!";

    fout.close();
}

int main()
{
    ReadData();
    WriteData(Solve());
    return 0;
}