#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

const int nmax = 50000;
const int oo = (1 << 31) - 1;

using namespace std;

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

int n, m, d[nmax], sol[nmax], ok;

vector<pair<int, int>> v[nmax + 1];
queue<pair<int, int>> c;

void citire() {
    f >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        v[x].push_back({y, c});
    }
    for(int i = 2; i <= n; ++i)
        d[i] = oo;
}

void malasatnevasta() {
    for(int i = 0; i < v[1].size(); ++i) {
        c.push({v[1][i].second, v[1][i].first});
        d[v[1][i].first] = v[1][i].second;
    }

    while(!c.empty()) {
        int x = c.front().second,
            cfrim = c.front().first;
        c.pop();

        if(d[x] < cfrim)
            continue;
        if(++sol[x] > n) {
            g << "Ciclu negativ!";
            ok = 1;
            return;
        }

        for(int i = 0; i < v[x].size(); ++i) {
            int y = v[x][i].first,
                k = v[x][i].second;

                if(d[y] > d[x] + k)
                    d[y] = d[x] + k,
                    c.push({d[y], y});
        }

    }
}

void afisare() {
    for(int i = 2; i <= n; ++i)
        g << d[i] << ' ';
}

int main()
{
    citire();
    malasatnevasta();
    if(!ok) afisare();
    f.close();
    g.close();
    return 0;
}