#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

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

int n,m,x,i,j,y,a,b,c,pret,sz,cost[50001];
bool ok;
vector <tuple<int,int,int>>v;

int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    while(m --)
    {
        f >> x >> y >> pret;
        v.push_back(make_tuple(x,y,pret));
    }
    sz = v.size();
    for(i = 1; i <= n; ++ i)
        cost[i] = inf;
    cost[1] = 0;
    for(i = 1; i < n; ++ i)
    {
        ok = 0;
        for(j = 0; j < sz; ++ j)
        {
            a = get<0>(v[j]);
            b = get<1>(v[j]);
            c = get<2>(v[j]);
            if(cost[a] != inf && cost[b] > cost[a] + c)
            {
                cost[b] = cost[a] + c;
                ok = 1;
            }
        }
        if(!ok)
            break;
    }
    for(j = 0; j < sz; ++ j)
    {
        a = get<0>(v[j]);
        b = get<1>(v[j]);
        c = get<2>(v[j]);
        if(cost[a] != inf && cost[b] > cost[a] + c)
        {
            cost[b] = cost[a] + c;
            g << "Ciclu negativ!";
            return 0;
        }
    }
    for(i = 2; i <= n; ++ i)
        if(cost[i] != inf)
            g << cost[i] << ' ';
}