#include <cstdio>
#include <vector>
#define nmax 50001
#define inf 0x3f3f3f3f
#define mmax 250001

using namespace std;

int N,M;
vector <pair<int,int> > V[nmax];
int cost[nmax];

void verif(){

  int i;
  for(i = 1;i <= N;i++)
    for(vector < pair < int , int > > :: iterator it = V[i].begin();it != V[i].end();++it)
      if(cost[i] + it->second < cost[it->first]){
	printf("Ciclu negativ!\n");
	return;
      }

  for(i = 2;i <= N;i++)printf("%d ",cost[i]);
  printf("\n");
  
}

int main(){

  freopen("bellmanford.in","r",stdin);
  freopen("bellmanford.out","w",stdout);

  scanf("%d %d ",&N,&M);
  int x,y,z,w;
  while(M--){
    scanf("%d %d %d ",&x,&y,&z);
    V[x].push_back(make_pair(y,z));
  }

  for(x = 2;x <= N;x++){
    cost[x] = inf;
    
  }

  cost[1] = 0;

  for(x = 1;x < N;x++){

    for(y = 1;y <= N;y++){
      for(vector <pair < int , int > > :: iterator it = V[y].begin();it != V[y].end();++it)
	if(cost[y] + it->second < cost[it->first])
	  cost[it->first] = cost[y] + it->second;
    }
    
  }

  verif();
  
  return 0;
  
}