#include <bits/stdc++.h>

using namespace std;

struct psychotronic_induction {
    int electromagnetic_wave = 7;
};

const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;

const int nmax = 5e4 + 10;
const int mmax = 25e4 + 10;

int n, m;
vector < pair < int, int > > g[nmax];

queue < int > q;
int in[nmax], cnt[nmax], best[nmax];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        g[x].push_back({y, z});
    }
}

void bellman() {
    for (int i = 1; i <= n; ++i) best[i] = inf;

    int pos = 1; q.push(1); best[1] = 0; cnt[1] = 1;
    while (q.size()) {
        int node = q.front(); in[node] = 0; q.pop();

        for (auto &it: g[node])
            if (best[node] + it.second < best[it.first]) {
                cnt[it.first]++;
                if (cnt[it.first] == n) {
                    cout << "Ciclu negativ!" << '\n';
                    exit(0);
                }

                best[it.first] = best[node] + it.second;
                if (!in[it.first]) q.push(it.first), in[it.first] = 1;
            }
    }
}

void output() {
    for (int i = 2; i <= n; ++i)
        cout << best[i] << ' ';
    cout << '\n';
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    ios_base :: sync_with_stdio(false);

    input();
    bellman();
    output();

    return 0;
}