#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e4 + 10;
const int inf = 0x3f3f3f3f;

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

void run_bellman() {
    queue < int > q;

    for (int i = 1; i <= n; ++i)
        bst[i] = inf, in[i] = 0;

    bst[1] = 0; q.push(1); in[1] = 1;
    while (q.size()) {
        int node = q.front(); q.pop(); in[node] = 0;
        for (auto &it: g[node]) {
            if (bst[it.first] <= bst[node] + it.second)
                continue;

            cnt[it.first]++;
            if (cnt[it.first] == n) {
                cout << "Ciclu negativ!\n";
                exit(0);
            }

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

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

    ios_base :: sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;

        g[x].push_back({y, c});
    }

    run_bellman();
    for (int i = 2; i <= n; ++i)
        cout << bst[i] << ' ';

    return 0;
}