#include <fstream>
#include <bitset>
#include <list>
#include <queue>

#define x first
#define y second
#define inf 300000000

using namespace std;

list<pair<int,int> > v[50005];
bitset<50005> viz;
int up[50005];
int d[50005];

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n,m,i,a,b,c;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        a--;
        b--;
        v[a].push_back(make_pair(b,c));
    }
    for(i=1;i<n;i++)
        d[i]=inf;
    bool oprit=false;
    queue<int> coada;
    coada.push(0);
    viz[0]=1;
    up[0]=1;
    list<pair<int,int> >::iterator it;
    while(!coada.empty())
    {
            for(it=v[coada.front()].begin();it!=v[coada.front()].end();it++)
            {
                if(d[it->x]>d[coada.front()]+it->y)
                {
                   d[it->x]=d[coada.front()]+it->y;
                   up[it->x]++;
                   if(up[it->x]>=n)
                   {
                       oprit=true;
                       break;
                   }
                   if(!viz[it->x])
                   {
                      coada.push(it->x);
                      viz[it->x]=1;
                   }
                }
            }
            if(oprit)
                break;
            viz[coada.front()]=0;
            coada.pop();
    }
    if(oprit)
    {
        cout<<"Ciclu negativ!\n";
    }
    else
    {
        for(i=1;i<n;i++)
            cout<<d[i]<<' ';
        cout<<'\n';
    }
    cin.close();
    cout.close();
    return 0;
}