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

int n,m,dist[maxm];

int bf()
{int a,b,c,v[100][100],n,m,dist[maxm],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<=n;i++)
  {dist[i]=infinit;
  dist[1]=0;
  if(bf())
  g<<"Ciclu negativ!";
  else
  for(i=2;i<=n;i++)
  g<<dist[i]<<"\n";}
  return 0;
}