#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

#define MAX_N 50001
#define mp make_pair
#define INF 9999999

vector < pair<int,int> > gr[MAX_N];
int n,m,d[MAX_N],nr[MAX_N];

void read(void)
{
	int i,x,y,c;
	freopen("bellmanford.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(i=1; i<=m; i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		gr[x].push_back(mp(y,c));
	}
}

int bellman_ford(int start)
{
	
	int i,x;
	queue <int> C;
	vector< pair<int,int> > ::iterator it;
	
	for(i=2; i<=n; i++) 
		d[i]=INF;
	C.push(start);  
	while(!C.empty())      
	{
		
		x=C.front();   
		C.pop();  
		
		for(it=gr[x].begin(); it!=gr[x].end(); it++)   
			if(d[it->first]>d[x]+it->second)          
			{
				d[it->first]=d[x]+it->second;   
				C.push(it->first);              
				nr[it->first]++;   
				if(nr[it->first]==n)   
 					return 0;
			}
	}
	return 1;
}

void write(void)
{
	int i;
	freopen("bellmanford.out","w",stdout);
	if(bellman_ford(1))
		for(i=2; i<=n; i++)
			printf("%d ",d[i]);
	else
		printf("Ciclu negativ!");
}
		
	
int main()
{
	read();
	write();
	return 0;
}