#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

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

const int INF = 2e9;
const int NM = 50010;
int N, E, src = 1, i, j;
int dist[NM];

struct Edge {
    int u, v, w;
};

vector <Edge> G;

int main()
{
    in >> N >> E;
    for (i = 1; i <= E; ++i) {
        Edge e;
        in >> e.u >> e.v >> e.w;
        G.push_back(e);
    }

    fill(dist, dist+N+1, INF);
    dist[src] = 0;

    for (i = 1; i <= N - 1; ++i) {
        for (j = 0; j < G.size(); ++j) {
            if (dist[G[j].u] + G[j].w < dist[G[j].v])
                dist[G[j].v] = dist[G[j].u] + G[j].w;
        }
    }

    for (i = 0; i < G.size(); ++i) {
        if (dist[G[j].u] + G[j].w < dist[G[j].v]) {
            out << "Ciclu negativ!";
            return 0;
        }
    }

    for (j = 2; j <= N; ++j) {
        out << dist[j] << ' ';
    }

    return 0;
}