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

using namespace std;

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

vector <int> ls[50005], lc[50005];
int n, m, x, y, c, l, i;
queue <int> q;
int viz[50005], cnt[50005];

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> c;
        ls[x].push_back(y);
        lc[x].push_back(c);
    }
    for (i = 2; i <= n; i++)
        viz[i] = 1000000005;
    q.push(1);
    while (q.empty()==0) {
        x = q.front();
        q.pop();
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            c = lc[x][i];
            if (viz[x]+c < viz[y]) {
                viz[y] = viz[x]+c;
                cnt[y]++;
                q.push(y);
            }
            if (cnt[y] >= n) {
                g << "Ciclu negativ!";
                return 0;
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << viz[i] << ' ';
    return 0;
}