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

#define maxn 50001
#define INF 1000000000

vector <int> vecini[maxn] ;
vector <int> cost[maxn] ;

int n,m ;
int d[maxn],nrcoada[maxn] ;
bool incoada[maxn] ;
int coada[maxn] ;
int len ;

int main()
{
	
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int a,b,c ;
		scanf("%d%d%d",&a,&b,&c);
		vecini[a].push_back(b) ;
		cost[a].push_back(c) ;
	}
	
	for(int i=1;i<=maxn;++i)
		d[i] = INF ;
	
	len = 1 ;
	coada[len] = 1 ;
	d[1] = 0 ;
	int x,y ;
	
	for(int i=1;i<=len;++i)
	{
		x = coada[i] ;
		incoada[x] = false ;
		
		for(size_t j=0;j<vecini[x].size();++j)
		{
			y = vecini[x][j] ;
			if( d[x] + cost[x][j] < d[y] )
			{
				d[y] = d[x] + cost[x][j] ;
				if( !incoada[y] )
				{
					++len ;
					coada[len] = y ;
					incoada[y] = true ;
					++ nrcoada[y] ;
					if( nrcoada[y] == n )
					{
						printf("Ciclu negativ!\n");
						return 0;
					}
				}
			}
		}
	}
	
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]);
	printf("\n");
	
	return 0;
	
}