#include <cstdio>
#include <list>

using namespace std;

const int INF = 0x7FFFFFFF;
const int NMAX = 500000;

int d[NMAX],n,m;

struct muchie
{
	int x;
	int y;
	int dist;
};

list<muchie> l;

void bellmanFord(int s)
{
	for(int i=1;i<=n;i++)
		d[i]=INF;
	d[s]=0;
	list<muchie>::iterator it;
	
	for(int i=1;i<n;i++)
	{
		for(it=l.begin();it!=l.end();++it)
			if(d[(*it).y]>d[(*it).x]+(*it).dist)
				d[(*it).y] = d[(*it).x]+(*it).dist;
	}
	for(it=l.begin();it!=l.end();++it)
		if(d[(*it).y]>d[(*it).x]+(*it).dist)
		{
			printf("Ciclu negativ!");
			return;
		}
	for(int i=1;i<=n;i++)
		if(i!=s)
			printf("%d ",d[i]);
	printf("\n");
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	muchie a;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&a.x,&a.y,&a.dist);
		l.push_back(a);
	}
	bellmanFord(1);
	return 0;
}