#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int,int> > v[50005];
pair<int,int> nr;
int n,m,x,y,c,viz[50005],ok,val[50005];
queue <int> q;
void parc(int nod)
{
    for(vector<pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        nr=*it;
        if(val[nod]+nr.second<val[nr.first] || viz[nr.first]==0)
        {
            q.push(nr.first);
            val[nr.first]=val[nod]+nr.second;
            viz[nr.first]++;
            if(viz[nr.first]>n)
                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;
}