#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

#define NMAX 50005
#define INF 99999999

using namespace std;

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

vector<vector<pair<int, int>>> gr;

int N, M;
int d[NMAX], cntQueue[NMAX];
bool inQueue[NMAX];


void setInf() {
    for (int i = 1; i <= N; ++i) {
        d[i] = INF;
    }
}

void read() {
    fin >> N >> M;
    gr.resize(N + 1);
    int x, y, w;
    for (int i = 1; i <= M; ++i) {
        fin >> x >> y >> w;
        gr[x].emplace_back(y, w);
    }
}

bool bellman_ford(int nod) {

    setInf();

    d[nod] = 0;

    queue<int> Q;
    Q.push(nod);
    inQueue[nod] = true;
    cntQueue[nod] = 1;

    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        inQueue[nod] = false;
        for (auto& v : gr[nod]) {
            if(d[nod] + v.second < d[v.first]) {
                d[v.first] = d[nod] + v.second;
                if (!inQueue[v.first]) {
                    Q.push(v.first);
                    cntQueue[v.first]++;
                    inQueue[v.first] = true;
                    if (cntQueue[v.first] > N) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main()
{
    read();
    bool ok = bellman_ford(1);

    if (ok) {
        for (int i = 2; i <= N; ++i) {
            fout << d[i] << " ";
        }
        fout << "\n";
    }
    else {
        fout << "Ciclu negativ!";
    }
    return 0;
}