#include<stdio.h>
#define maxn 50005
#define infinity 1001
using namespace std;

long n, m, i, j, dist[maxn], v[maxn][3], x, y, c;

void bellman_ford()
{for(i=1; i<=n-1; i++)   
    for(j=1; j<=m; j++)
       {x=v[j][0];
        y=v[j][1]; 
        c=v[j][2];
        if(dist[x]+c<dist[y])
          dist[y]=dist[x]+c;     
       }      
}

int is_negative()
{for(i=1; i<=m; i++)
     {x=v[i][0];
      y=v[i][1]; 
      c=v[i][2];
      if(dist[x]+c<dist[y])
        return 1;
     }
return 0;
}

int main()
{freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
    
scanf("%d %d", &n, &m);   

for(i=1; i<=m; i++)
   {scanf("%d %d %d", &x, &y, &c); 
    v[i][0]=x;
    v[i][1]=y;
    v[i][2]=c;
   }  
   
dist[1]=0;
for(i=2; i<=n; i++) 
   dist[i]=infinity;   

bellman_ford();

if(is_negative()==1) 
   printf("Ciclu negativ!");  
else for(i=2; i<=n; i++)
        printf("%d ", dist[i]);

return 0;  
}