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

using namespace std;

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

int n, m;

bool ok = 0;

vector <pair <int, int> > a[50005];

vector <int> cost(50005, 1e9), cnt(50005, 0);

queue <int> q;

void bellmanford()
{
    q.push(1);

    cost[1] = 0;

    while (!q.empty()) {
        int nod = q.front();

        q.pop();

        for (auto vecin : a[nod]) {
            if (cost[nod] + vecin.second < cost[vecin.first]) {
                cost[vecin.first] = cost[nod] + vecin.second;
                q.push(vecin.first);

                cnt[vecin.first]++;

                if (cnt[vecin.first] > n) {
                    g << "Ciclu negativ!";
                    ok = 1;
                    return;
                }
            }
        }
    }
}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y, z;

        f >> x >> y >> z;

        a[x].push_back({y, z});
    }

    bellmanford();

    if (ok) {
        return 0;
    }

    for (int i = 2; i <= n; ++i) {
        g << cost[i] << ' ';
    }

    return 0;
}