#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

#define maxn 50001
#define INF 1<<30 

struct NOD
{int y,cost;};

int n,m;
int d[maxn],nrq[maxn] ;
bool inq[maxn] ;
vector <NOD> graf[maxn];
queue <int> q ;

int main()
{
	
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	int x,y,cost;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&cost);
		graf[x].push_back( (NOD){y,cost} ) ;
	}
	
	for(int i=1;i<=maxn;++i)
		d[i] = INF ;
	
	q.push(1);
	d[1]=0;
	
	while( !q.empty() )
	{
		x = q.front() ;
		q.pop() ;
		inq[x] = false ;
		
		for(size_t i=0;i<graf[x].size();++i)
		{
			y = graf[x][i].y ;
			if( d[x] + graf[x][i].cost < d[y] )
			{
				d[y] = d[x] + graf[x][i].cost ;
				if( !inq[y] )
				{
					q.push(y) ;
					inq[y] = true ;
					++ nrq[y] ;
					if( nrq[y] == n )
					{
						printf("Ciclu negativ!\n");
						return 0;
					}
				}
			}
		}
	}
	for(int i=2;i<=n;++i)
	{
		if( d[i]==INF ) 
			printf("%d ",0);
		else
			printf("%d ",d[i]);
	}
	printf("\n");
	
	return 0;

}