#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define NMAX 50005

using namespace std;

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

struct A
{
    int y, cost;
};

vector < A > v[NMAX];
queue < int > q;
map < pair < int, int >, int > M;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0);
    int n, m, x, y, z, i, r[NMAX];
    bool ok, fr[NMAX];

    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        v[x].pb({y, z});
    }

    for(i = 1; i <= n; i++) fr[i] = 0, r[i] = INT_MAX;
    ok = 1, r[1] = 0, fr[1] = 1, q.push(1);
    while(q.empty() == 0 && ok == 1)
    {
        x = q.front(), q.pop();

        fr[x] = 0;
        for(auto it:v[x])
            if(r[x] + it.cost < r[it.y])
            {
                if(M[{x,it.y}] == 0) M[{x,it.y}] = 1;
                else
                {
                    fout << "Cicle negativ!";
                    ok = 0;
                    break;
                }
                r[it.y] = r[x] + it.cost;
                if(fr[it.y] == 0) q.push(it.y);
            }
    }

    if(ok == 1) for(i = 2; i <= n; i++) fout << r[i] << ' ';


    return 0;
}