#include<stdio.h>
#include<fstream.h>
#define inf 1000000000
using namespace std;

struct muchie {long x,y,c;
              } z[250010];
long n,m,i,j,cost[50010],cy;
int main() {
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%ld %ld",&n,&m);
for (i=1;i<=m;i++)
    scanf("%ld %ld %ld\n",&z[i].x,&z[i].y,&z[i].c);
cost[1]=0;
for (i=2;i<=n;i++)
    cost[i]=inf;
for (i=1;i<=n-1;i++)
    for(j=1;j<=m;j++)
       if (cost[z[j].x]+z[j].c<cost[z[j].y])
           cost[z[j].y]=cost[z[j].x]+z[j].c;
cy=0;
for(j=1;j<=m;j++)
   if (cost[z[j].x]+z[j].c<cost[z[j].y]) cy=1;
if (cy) { printf("ciclu neg\n");
          return 0;}
for (i=2;i<=n;i++)
  printf("%ld ",cost[i]);

return 0;
}