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

using namespace std;

FILE *f,*s;

int i,j,k,l,m,n;

int v2[50005],v3[50005],v4[50005];

vector <pair <int, int> > v1[50005];

queue <int> q;

int main()
{
	f=fopen("bellmanford.in","r");
	s=fopen("bellmanford.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		int a,b,c;
		
		fscanf(f,"%d %d %d",&a,&b,&c);
		
		v1[a].push_back(make_pair(b, c)); 
	}
	
	q.push(1); 
    
	v2[1]=v3[1]=1; 
    
	for (i=2;i<=n;i++) 
		v4[i]=50000001; 
    
	while(!q.empty()) 
	{         
		
		int x=q.front();
		
		q.pop(); 
        
		v3[x]=0; 
 
		for(j=0;j<v1[x].size();j++)
		{	
			if(v4[x]+v1[x][j].second<v4[v1[x][j].first]) 
			{ 
				v4[v1[x][j].first]=v4[x]+v1[x][j].second; 
 
				if (v2[v1[x][j].first]<n&&!v3[v1[x][j].first]) 
				{ 
					q.push(v1[x][j].first); 
                    
					v2[v1[x][j].first]++;
					v3[v1[x][j].first]=1; 
				} 
            
			}
		}	
	}
   
	for (i=1;i<=n;i++)
	{	
		for (j=0;j<v1[i].size();j++)
		{	
			if (v4[i]+v1[i][j].second<v4[v1[i][j].first]) 
			{ 
				printf("Ciclu negativ!\n"); 
                
				return 0; 
			}
		}	
    }
	
	for (i=2;i<=n;i++) 
		fprintf(s,"%d ",v4[i]); 
	
	fprintf(s,"\n"); 
	
	fclose(s);
	
	return 0;
}