/* o singura sursa, toate destinatiile
inclusiv muchii cu costuri negative
1)daca are cilcuri negative, nu pot afisa o cea mai mica solutie, ar intra in cliclu infinit
pt un nod drumul ar trece la infinit prin acel ciclu pt a minimiza costul.....
2)daca n-are cicluri negative, e ok, pot afisa un cel mai mic cost
*/

#include <stdio.h>
#include <vector>
#define INF 250000010

using namespace std;

struct s{
   int nod;
   int cost;
};


vector <s> lista[50005];
int d[50005];//max 50000 de noduri; dist minima de la nodul 0 la nodul i
int n,l[50005];

int main(){
   int m;
   s aux;
   FILE *fin=fopen("bellmanford.in","r");
   FILE *fout=fopen("bellmanford.out","w");
   fscanf(fin,"%d %d",&n,&m);
   //init vectorul de distante
   int i,j,a,b,c;
   for(i=1;i<n;i++)d[i]=INF;
   for(i=0;i<m;i++){
      fscanf(fin,"%d%d%d",&a,&b,&c);
      aux.nod=b-1;
      aux.cost=c;
      lista[a-1].push_back(aux);
      l[a-1]++;
   }
  //de test...afisez datele
  /*for(i=0;i<n;i++){
    printf("%d: ",i);
    for(j=0;j<l[i];j++)printf("%d, ",lista[i][j].nod);
    printf("\n");
  } */ 

   //incep algoritmul
  d[0] = 0;
  int k;
  for (i = 0; i < (n-1); i++)
    for(k=0;k<n;k++)	
       for (j = 0; j < l[k]; j++)// consider muchia de la k la lista[k][j]
		if ((d[k] + lista[k][j].cost) < d[lista[k][j].nod])
				d[lista[k][j].nod] = d[k] + lista[k][j].cost;

   //mai incerc o imbunatatire..daca merge->ciclu negativ
	
        for(k=0;k<n;k++)	
            for (j = 0; j < l[k]; j++)// consider muchia de la i la lista[i][j]
		if (d[k] + lista[k][j].cost < d[lista[k][j].nod]){
                  fprintf(fout,"Ciclu negativ!\n");fclose(fout);     
                return 0;
         }


   for(i=1;i<n;i++){
      fprintf(fout,"%d ",d[i]);
   }


   fprintf(fout,"\n");
   fclose(fout);
return 0;
}