#include<fstream>
using namespace std;
int n,m;
struct nod{
       int info;
       int cost;
       nod *next;};
nod *g[50005];
int d[50005],v[50005],apariti[50005];
void adauga(int a,int b,int c);
int bellman();
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    int i;
    for(i=1;i<=m;i++)
     {
        int a,b,c;
        fin>>a>>b>>c;
        adauga(a,b,c);
     }
    for(i=1;i<=n;i++)
      d[i]=2000000000;
    if(bellman())
      fout<<"Ciclu negativ!";
    else
      for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}
 struct coada{
      int capat;
      coada *next;  
        };
 int bellman()
 {
   coada *st,*dr,*q;
   st=new coada;
   st->capat=1;
   st->next=NULL;
   v[1]=1;
   d[1]=0;
   dr=st;
   while(st)
   {
      int k=st->capat;
      v[k]=0;
      if(d[k]<2000000000)
        for(nod *p=g[k];p;p=p->next)
          if(d[p->info]>d[k]+p->cost)
           {  
             d[p->info]=d[k]+p->cost;
             if(v[p->info]==0)
             {
               if(apariti[p->info]>n)
                   return 1;
              q=new coada; 
              q->capat=p->info;
              q->next=NULL;
              dr->next=q;
              dr=q;
              apariti[p->info]++;
              v[p->info]=1;
           }
         }
        coada *u=st;
        st=st->next;
        delete u;
      }
   return 0;
}                                                                 
void adauga(int a,int b,int c)
{
     nod *t;
     t=new nod;
     t->info=b;
     t->cost=c;
     t->next=g[a];
     g[a]=t;
}