#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <climits>
#include <fstream>
#define VMAX 50000

using namespace std;

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

int V, E, x, y, c;
bool inQueue[VMAX];
int nr[VMAX];
int d[VMAX];
vector < pair <int, int> > adj[VMAX];

bool bellmanFord() {
    int u, w, cost;
    queue <int> q;

    q.push(0);
    d[0] = 0;
    inQueue[0] = true;

    while (!q.empty()) {
        u = q.front(), q.pop();
        inQueue[u] = false;

        ++nr[u];
        if (nr[u] >= V) return false;

        for (auto pereche:adj[u]) {
            w = pereche.first;
            cost = pereche.second;
            if (d[u] != INT_MAX && d[u] + cost < d[w]) {
                d[w] = d[u] + cost;
                if (!inQueue[w]) {
                    q.push(w);
                    inQueue[w] = true;
                }
            }
        }
    }
    return true;
}

int main()
{
    fin >> V >> E;

    while (E--) {
        fin >> x >> y >> c;
        adj[x - 1].push_back({y - 1, c});
    }

    for (int i = 0; i < V; ++i) d[i] = INT_MAX;

    bool res = bellmanFord();

    if (res) for (int i = 1; i < V; ++i) fout << d[i] << " ";
    else fout << "Ciclu negativ!";

    fin.close();
    fout.close();
    return 0;
}