#include<fstream>
using namespace std;
#define infinit 1111111
#define maxn 50001
#define maxm 250001
ifstream f("bellmanford.in.txt");
ofstream g("bellmanford.out.txt");

int n,m,dist[maxm],x,y,c,v[maxm][3];

int bf()
{int a,b,c,ok=0;
for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {a=v[j][0];
   b=v[j][1];
   c=v[j][2];
   if(dist[a]+c<dist[b])
   { dist[b]=dist[a]+c;
    ok=1;}
    if(dist[b]+c<dist[a])
    {dist[a]=dist[b]+c;}
     ok=1;}
      return ok;}
      
int main()
{f>>n>>m;
for(int i=1; i<=m; i++)
   {f>>x>>y>>c;
    v[i][0]=x;
    v[i][1]=y;
    v[i][2]=c;
   } 
 for(int j=1;j<=n;j++)
  {dist[j]=infinit;
  dist[1]=0;
  if(bf())
  g<<"Ciclu negativ!";
  else
  for(j=2;j<=n;j++)
  g<<dist[j]<<"\n";}
  return 0;
}