#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int i,j,N,M;
const int inf=1e9;
const int maxim=50000;
struct triplet
{
    int x,y,cost;
};
 bool comparare(const triplet& a,const triplet& b)
{
    return a.cost<b.cost;
}
int dist[maxim];
vector <triplet> G;

void BellmanFord()
{
    sort(G.begin(),G.end(),comparare);
  //  cout<<G[1].cost<<' ';
    for(i=0;i<=N-1;i++)
    {
        dist[i]=inf;
    }
    dist[0]=0;
//cout<<"DA";
for(i=1;i<=N-1;i++)
    {for(j=0;j<=M-1;j++)
    {
        triplet s;
        s=G[j];
       if(dist[s.x]!=inf && dist[s.x]+s.cost<dist[s.y])
       {
           dist[s.y]=dist[s.x]+s.cost;
       }
   }
}
//cout<<"DA";
   for(i=0;i<=M-1;i++)
   {
       triplet q;
       q=G[i];
       if(dist[q.x]!=inf && dist[q.x]+q.cost<dist[q.y])
       {
     //      cout<<i<<' ';
           fout<<"Ciclu negativ!";
           return;
       }
   }
   //cout<<"DA";
   for(i=1;i<=N-1;i++)
   {
       fout<<dist[i]<<' ';
   }
}
int main()
{
    //cout<<inf<<' ';
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        int a,b,c;
        triplet t;
        fin>>a>>b>>c;
       // cout<<a<<b<<' '<<c<<'\n';
        t.x=a;
        t.y=b;
        t.cost=c;
        G.push_back(t);
    }
    BellmanFord();
    return 0;
}