#include <stdio.h>
#include <vector>

#define INF 2000000000
#define NMAX 50005
using namespace std;

struct NOD{
   int nod;
   int cost;
};


vector <NOD> lista[NMAX];
int d[NMAX],l[NMAX];
bool s[NMAX];
int coada[NMAX];//va tine indicii nodurilor
int frecv[NMAX];
int li,ls;

int main(){
  int i,j,a,b,c;
  int n,m;
  NOD aux;
  FILE *fin=fopen("bellman.in","r");
  FILE *fout=fopen("bellman.out","w");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;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]++;
   }

  s[0]=1;//multimea nodurilor selectate, care sunt la un mom dat in coada
  d[0]=0;
  li=0;ls=1;
  coada[li]=0;
  while(ls!=li){
    for(j=0;j<l[coada[li]];j++){
        if(d[lista[coada[li]][j].nod]>d[coada[li]]+lista[coada[li]][j].cost){
          d[lista[coada[li]][j].nod]=d[coada[li]]+lista[coada[li]][j].cost;
          if(s[lista[coada[li]][j].nod]==0){
             if(frecv[lista[coada[li]][j].nod]<=n){
               coada[ls++]=lista[coada[li]][j].nod;
               frecv[lista[coada[li]][j].nod]++;
               ls=ls%50000;
               s[lista[coada[li]][j].nod]=1;
             }else{fprintf(fout,"Ciclu negativ!\n");return 0;}
           }
        }
    }
  li++;//am scos nodul coada[li] din coada..trebuie sa marchez asta
  s[coada[li-1]]=0;
  li=li%50000;
 }
 
    for(i=1;i<n;i++){
            fprintf(fout,"%d ",(d[i]==INF?0:d[i]));
    }
    fprintf(fout,"\n");
  
  
return 0;    
}