#include<stdio.h>
#define maxn 50005
#define maxm 250025
#define infinity 2718281
using namespace std;

int n, m, i, dist[maxn], ok=1, j, v[maxm][3], x, y, c;

void bellman_ford()
{for(i=1; i<=n-1 && ok==1; i++)   
    {ok=0;
     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;
            ok=1;
           }     
        }  
    }    
}

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())  
  printf("Ciclu negativ!");
else for(i=2; i<=n; i++)
        printf("%d ", dist[i]);

return 0;  
}