#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 5e4 + 1;

int n, m;
vector<pair<int, int>> v[NMAX]; // vecin, cost
bool inQueue[NMAX];
queue<int> Q;
int cnt_inQueue[NMAX], dist[NMAX];

int main()
{
    fin >> n >> m;
    int x, y, z;
    for (; m; --m) {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    memset(dist, 0x3f, NMAX);
    inQueue[1] = 1;
    dist[1] = 0;
    Q.push(1);
    bool negativ = 0;
    while (Q.size() && !negativ) {
        x = Q.front();
        Q.pop();
        inQueue[x] = 0;
        for (auto y: v[x]) {
            if (dist[x] < 0x3f3f3f3f) {
                if (dist[y.first] > dist[x] + y.second) {
                    dist[y.first] = dist[x] + y.second;
                    if (!inQueue[y.first]) {
                        if (cnt_inQueue[y.first] > n)
                            negativ = 1;
                        else {
                            Q.push(y.first);
                            inQueue[y.first] = 1;
                            cnt_inQueue[y.first]++;
                        }
                    }
                }
            }
        }
    }
    if (negativ) {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (int i = 2; i <= n; ++i)
        fout << dist[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}