#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int INF=0x3f3f3f3f;
const int Nmax=50000+5;
vector <pair<int,int> >v[Nmax];
queue <int> Q;
int DP[Nmax];
bool inq[Nmax],ok;
int c[Nmax],nod,n,m;
void BF()
{
    if(!Q.empty()){
    nod=Q.front();
    Q.pop();
    }else return;
    //cout<<nod<<" ";
    if(ok==1)return;
    inq[nod]=0;
    for(auto i : v[nod])
        if(inq[i.first]==0 && (c[i.first]==0 or DP[i.first]>DP[nod]+i.second))
        {
            DP[i.first]=DP[nod]+i.second;
            inq[i.first]=1;
            c[i.first]++;
            if(c[i.first]>n)
                ok=1;
            if(i.first!=0)Q.push(i.first);
        }
        else if(inq[i.first]!=0)
        {
            c[i.first]++;
            if(c[i.first]>n)
                ok=1;
            DP[i.first]=DP[nod]+i.second;
        }
    BF();
}
int main()
{
    fin>>n>>m;
    for(int i=1,x,y,c;i<=m;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=0;i<=n;++i)DP[i]=INF;
    DP[1]=0;c[1]=0;
    Q.push(1);
    inq[1]=1;
    //for(int i=1;i<=n;++i,fout<<'\n')
        //for(int j=0;j<v[i].size();++j)fout<<v[i][j].first<<" ";
    BF();
    if(ok==1)
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;++i)fout<<DP[i]<<" ";
    return 0;
}