#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],x,y,c,v[maxm][3];

int bf()
{int a,b,c,ok=1;
for(int i=1;i<=n && ok==1;i++)
   {ok=0;
    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;
          }
       }
    }  
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(int j=2;j<=n;j++)
           g<<dist[j]<<" ";
  return 0;
}