#include<cstdio>
#include<fstream>
#include<vector>
#include<queue>
  
#define INFINIT 1<<30
#define DIM 50001
  
using namespace std;
  
    int drum[DIM];
     
  
vector< pair<int,int> >graf[DIM];
  
void set_inf(int n)
{
      for(int i=1;i<=n;++i)
      {
        drum[i]=INFINIT;
    }
}
 
int ciclu[DIM];
int ok;
 
void print (int start,int n)
{
    if (ok)
      {for(int i=1;i<=n;++i){
        if(drum[i]==INFINIT)
            drum[i]=0;
  
        if(start!=i)
            printf("%d ",drum[i]);}
        
    }
      else
          printf("Ciclu negativ!\n");
}
 
 
 
void bellford(int start,int n){
  
 
    int nod;
    queue <int> queue_graf;
  
    set_inf(n);
   
  
    drum[start]=0;
    queue_graf.push(start);
    ok=1;
  
    while(queue_graf.empty()==0){
  
        nod=queue_graf.front();
        queue_graf.pop();
  
        for( int i=0; i<graf[nod].size();++i ){
  
            if(drum[nod]+graf[nod][i].second<drum[graf[nod][i].first])
                if (ciclu[graf[nod][i].first]<n)
            {
  
                drum[graf[nod][i].first]=drum[nod]+graf[nod][i].second;
                queue_graf.push(graf[nod][i].first);
                ciclu[graf[nod][i].first]++;
            }
                else
                    ok=0;
  
        }
  
    }
  print(start,n);
  
}
  
 
 
int main(){
    freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
    int A,B,C,n,m;
  
  scanf("%d%d",&n,&m);
    for(int j=1;j<=m;j++){
  
            scanf("%d %d %d",&A,&B,&C);
            graf[A].push_back(make_pair(B, C));
  
        }
  
    bellford(1,n);
 
    
}