#include <cstdio>
#include <vector>
#include <queue>
#define inf 1000000000
#define nmax 50001
using namespace std;
FILE *f,*g;

int n,m;
int d[nmax], nr[nmax];
bool negativ;
vector < pair<int,int> > G[nmax];
queue <int> C;

void read()
{int i;
 int x,y,c;
 fscanf(f,"%d%d",&n,&m);
 for(i=1;i<=m;i++)
   {fscanf(f,"%d%d%d",&x,&y,&c);
    G[x].push_back(make_pair(y,c));
   }
}

void bellman_ford()
{int i,x;
 vector < pair<int,int> > ::iterator it;
 for(i=1;i<=n;i++) d[i]=inf;
 d[1]=0;
 C.push(1);
 while(!C.empty()&&!negativ)
  {x=C.front(); C.pop();
   for(it=G[x].begin();it!=G[x].end();++it)
     if(d[it->first]>d[x]+it->second)
     {d[it->first]=d[x]+it->second;
      nr[it->second]++;
      C.push(it->first);
      if(nr[it->first]>n) negativ=true;
     }
  }
}

void write()
{if(negativ) fprintf(g,"Ciclu negativ!\n");
 else
  {for(int i=1;i<=n;i++)
     if(i!=1) fprintf(g,"%d ",d[i]!=inf?d[i]:0);
   fprintf(g,"\n");
  }

}


int main()
{
 f=fopen("bellmanford.in","r");
 g=fopen("bellmanford.out","w");
 read();
 bellman_ford();
 write();
 return 0;
}