#include <bits/stdc++.h>

using namespace std;

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

const int Dim = 1e5 + 5;
const int Inf = 1e9 + 5;

int d[Dim], modif[Dim];
int n, m, s;

bool inQueue[Dim];

queue <int> coada;

vector <pair<int, int> > G[Dim];

bool bellman_ford(int s) {
    for(int i = 1; i <= n; ++i) d[i] = Inf;
    d[s] = 0; modif[s] = 1;

    coada.push(s);
    while(!coada.empty()) {
        int node = coada.front();
        coada.pop();

        inQueue[node] = false;
        for(auto it = G[node].begin(); it != G[node].end(); ++it) {
            if(d[node] + it -> second < d[it -> first]) {
                d[it -> first] = d[node] + it -> second;
                if(inQueue[it -> first] == false) {
                    ++modif[it -> first];
                    if(modif[it -> first] >= n) {
                        return true;
                    }

                    inQueue[it -> first] = true;
                    coada.push(it -> first);
                }
            }
        }
    }

    return false;
}

int main() {
    f >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        G[x].push_back({y, cost});
    }

    //cin >> s;
    if(bellman_ford(1) == true) {
        g << "Ciclu negativ!\n";
        return 0;
    }

    for(int i = 2; i <= n; ++i) {
        g << d[i] << " ";
    }
    return 0;
}