#include <fstream>
using namespace std;
#define nmax 50001
#define inf 1<<18
typedef struct nod
 {
 nod *urm;
 int x,c;
 } graf;
graf *G[nmax];
int nr[nmax];
bool viz[nmax];
int n,Q[10*nmax];
long dist[nmax];
void add(graf *&g,int x,int c)
 {
 graf *p=new graf;
 p->x=x;
 p->c=c;
 p->urm=g;
 g=p;
 }
void read()
 {
 ifstream f("bellmanford.in");
 int m,i,x,y,c;
 f>>n>>m;
 for(i=0;i<m;++i)
  {
  f>>x>>y>>c;
  add(G[x],y,c);
  }
 }
bool bf()
 {
 int i,k=0,x;
 Q[++k]=1;
 dist[k]=0;
 for(i=2;i<=n;++i)
  dist[i]=inf;
 for(i=1;i<=k;++i)
  {
  x=Q[i];
  viz[x]=false;
  for(graf *g=G[x];g!=NULL;g=g->urm)
   if(dist[g->x]>dist[x]+g->c)
    {
    ++nr[g->x];
	if(nr[g->x]>n)
	 return true;
    dist[g->x]=dist[x]+g->c;
	if(!viz[g->x])
	 {
	 Q[++k]=g->x;
	 viz[g->x]=true;
	 }
    }
  }
 return false;
 }
int main()
 {
 read();
 ofstream g("bellmanford.out");
 if(bf())
  g<<"Ciclu negativ!";
 else for(int i=2;i<=n;++i)
  g<<dist[i]<<" ";
 return 0;
 }