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

#define inf 250000001

using namespace std;


vector<int> vecini[50001];
vector<int> costuri[50001];
queue<int> coada;
int lung[50001];

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	int n,m,d[50001],x,y,c;
	scanf("%d %d",&n,&m);
	printf("lala%d",n);
	for(int i=1; i<=n; ++i) d[i]=inf; 	
	for(int i=1; i<=m; ++i)
	{
		scanf("%d %d %d", &x,&y,&c);
		vecini[x].push_back(y);
		costuri[x].push_back(c);
	}

	int depasit=0;
	coada.push(1);
	while(!coada.empty()&&!depasit)
	{
			for(int k=0; k<vecini[coada.front()].size(); ++k)
				if( d[vecini[coada.front()][k]]>d[coada.front()]+costuri[coada.front()][k] )
				{
					d[vecini[coada.front()][k]]=d[coada.front()]+costuri[coada.front()][k];
					coada.push( vecini[coada.front()][k] );
					lung[ vecini[coada.front()][k] ] ++;
					if( lung[ vecini[coada.front()][k] ] >=n ) depasit=1;
				}
		coada.pop();
				
	}
	
	if(depasit) printf("Ciclu negativ!");
	else for(int i=2; i<=n; ++i) printf("%d ",d[i]);
	return 0;
}