#include <fstream>
#include <queue>
using namespace std;
ifstream cin ("bellmanford.in");
ofstream cout("bellmanford.out");
queue <int> Q;
typedef struct celula {
                       int nod;
                       int cost;
                       celula* next;
                       }*lista;
const int INF=1<<20;

int n,i,a,b,v,k(0),j,m,l,D[300013],aux,viz[300013],p,c;
lista lda[72013],r;

void add(int nod,int cost,lista &p)
{
  lista r=new celula;
  r->nod=nod;
  r->cost=cost;
  r->next=p;
  p=r;
}  

int main()
{
  cin>>n>>p;
  aux=n; D[1]=0; 
  while(cin>>a>>b>>c) add(b,c,lda[a]);
  for (i=1;i<=n;++i) viz[i]=0;
  for (i=2;i<=n;++i) D[i]=INF;
  Q.push(1);
  while(!Q.empty() && !k){
                          v=Q.front();
                          r=lda[v];        
                          while(r){
                                   if (D[v]+r->cost<D[r->nod]) {
                                                                ++viz[r->nod];
                                                                if (viz[r->nod]==n){
                                                                                    k=1;
                                                                                    break;
                                                                                    }  
                                                                 D[r->nod]=min(D[v]+r->cost,D[r->nod]);
                                                                 Q.push(r->nod);
                                                                 }  
                                             r=r->next;
                                            }
                          Q.pop(); 
                        }
if (k) cout<<"Ciclu negativ!";
     else
for (i=2;i<=aux;++i)
    if (D[i]==INF) cout<<"0 ";
                 else cout<<D[i]<<" ";
return 0;
}