#include <cstdio>
#include <list>
#include <queue>

using namespace std;

const int INF = 0x3FFFFFFF;
const int NMAX = 500001;

queue<int> q;
list<pair<int,int> > l[NMAX];
int n,m,d[NMAX];
int v[NMAX];
int nrInCoada[NMAX];

void bellmanFord(int s)
{
	for(int i=1;i<=n;i++)
	{
		d[i]=INF;
		v[i]=1;
	}
	d[s]=0;
	list<pair<int,int> >::iterator it;
	bool cicluNegativ = false;
	
	while(!q.empty() && !cicluNegativ)
	{
		int x = q.front();
		q.pop();
		v[x] = 0;
		for(it = l[x].begin(); it != l[x].end(); ++it)
		{
			if(d[(*it).first] > d[x] + (*it).second)
			{
				d[(*it).first] = d[x] + (*it).second;
				if(v[(*it).first] == 0)
				{
					q.push((*it).first);
					v[(*it).first] = 1;
					nrInCoada[(*it).first]++;
					if(nrInCoada[(*it).first]>n)
						cicluNegativ = true;
				}
			}
		}
	}
	if(cicluNegativ)
		printf("Ciclu negativ!");
	else 
	{
		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);
	int x,y,dist;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&dist);
		l[x].push_back(make_pair(y,dist));
	}
	for(int i=1;i<=n;i++)
		q.push(i);
	bellmanFord(1);
	return 0;
}