#include <bits/stdc++.h>
#define NMAX 50005
#define pii pair <int, int>

using namespace std;

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

int n, m, x, y, c, ok;
int viz[NMAX],val[NMAX];

pii nr;
vector<pii> v[NMAX];
queue <int> q;

void parc(int nod)
{
    for (vector<pii>::iterator it = v[nod].begin(); it != v[nod].end(); it++)
    {
        nr = *it;
        int nxt = nr.first;
        int cst = nr.second;
        if (val[nod] + cst < val[nxt] || viz[nxt] == 0)
        {
            q.push(nxt);
            val[nxt] = val[nod] + cst;
            viz[nxt]++;
            if(viz[nxt] > n) ///Detects a negative cycle
                ok = 1;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
    q.push(1);
    while (!q.empty() && ok == 0)
    {
        parc(q.front());
        q.pop();
    }
    if (ok == 1)
        fout << "Ciclu negativ!\n";
    else
        for (int i = 2; i <= n; i++)
            fout << val[i] << " ";
    return 0;
}