#include<fstream>

using namespace std;

#define NMAX 50003
#define MMAX 250003
#define INF 1000000000

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

struct edge {
  int a,b,c;
} e[MMAX];

int n,m,i,j;
int cost[NMAX];

int main() {
  fi>>n>>m;
  for(i=1;i<=m;i++) fi>>e[i].a>>e[i].b>>e[i].c;
  fi.close();
  for(i=2;i<=n;i++) cost[i]=INF;
  for(i=1;i<n;i++)
   for(j=1;j<=m;j++)
    if(cost[e[j].a]+e[j].c<cost[e[j].b])
     cost[e[j].b]=cost[e[j].a]+e[j].c;
  for(i=1;i<=m;i++)
   if(cost[e[j].a]+e[j].c<cost[e[j].b]) {
     fo<<"Ciclu negativ!\n";
     fo.close();
     return 0;
   }
  for(i=2;i<=n;i++) fo<<cost[i]<<" ";
  fo<<"\n";
  fo.close();
  return 0;
}