#include<stdio.h>
int n,m, cost[250000],pred[50000],dist[50000];
struct arce{int a;
           int b;}arc[250000];


void bellmanford(){
    int i,j,pp;
    for(i=1;i<=n-1;i++){
       pp=0;
       for(j=1;j<=m;j++)
           if(dist[arc[j].a]+ cost[j] < dist[arc[j].b]){
               dist[arc[j].b]=dist[arc[j].a]+ cost[j];
               pred[arc[j].b]=arc[j].a;
               pp=1;
           }
    if(pp==0)
       i=n;
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=m;i++)
  scanf("%d%d%d",&arc[i].a,&arc[i].b,&cost[i]);
for(i=1;i<=n;i++){
    if(i==1)
       dist[i]=0;
    else
       dist[i]=2000000001;
    pred[i]=0;
}
bellmanford();

for(i=1;i<=m;i++)
    if(dist[arc[i].a]+ cost[i] < dist[arc[i].b])
        {printf("Ciclu negativ!");
         return 0;
        }
for(i=2;i<=n;i++)
   printf("%d ",dist[i]);
return 0;
}