#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);

   
}