#include <bits/stdc++.h>

using namespace std;

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

struct drumuri{
    int node,cost;
};

int n,m,x,y,z,drum[50200],inque[50200],ciclu[50200];
vector <drumuri> edges[50200];
queue <int> q;

bool bellman()
{
    for(int i=2; i<=n; i++)
        drum[i]=INT_MAX;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        inque[x]=0, q.pop();
        for(auto y:edges[x])
            if(drum[x]+y.cost<drum[y.node])
            {
                ciclu[y.node]++;
                if(ciclu[y.node]>=n)
                    return 1;
                drum[y.node]=drum[x]+y.cost;
                if(inque[y.node]==0)
                    q.push(y.node), inque[y.node]=1;
            }
    }
    return 0;
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges[x].push_back({y,z});
    if(bellman())
        g<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            g<<drum[i]<<' ';
    return 0;
}