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

using namespace std;

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

const int inf = 1 << 30, maxn = 50005;

int n, m, i, x, y, c;

struct xy {
    int x, y;
};

vector <xy> nod[maxn];

void negative() {
    g << "Ciclu negativ!";
    exit(0);
}

int a[maxn], done[maxn], is[maxn], ans[maxn], j, ok;
queue <int> q;
int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y >> c;
        nod[x].push_back({y, c});
    }
    for(i = 2; i <= n; i ++) {
        ans[i] = inf;
    }

    q.push(1);
    done[1] ++;
    while(!q.empty()) {
        j = q.front();
        is[j] = false;
        q.pop();
        for(auto u : nod[j]) {
            if(ans[j] + u.y < ans[u.x]) {
                if(done[j] >= n) {
                    negative();
                }
                ans[u.x] = ans[j] + u.y;
                if(is[u.x] == true) {
                    continue;
                }
                done[u.x] ++;
                q.push(u.x);
                is[u.x] = true;
            }
        }
    }
    if(ok == true) {
        negative();
    }
    for(i = 2; i <=n; i ++) {
        if(ans[i] == inf) {
            g << "0 ";
        } else {
            g << ans[i] << ' ';
        }
    }

    f.close(); g.close();
    return 0;
}