#include <cstdio>
#include <vector>
#define fi first
#define se second
using namespace std;
int n,m,k=0;
vector<pair<int, int> > a[50050];
int cost[50050],coada[1000050],trec[50050];
bool marc[50050];

void bfs()
{
	int p,r=1;
	coada[1]=1;
	for (p=1;p<=r;++p)
	{
		marc[coada[p%1000000]]=0;
		for (int i=0;i<a[coada[p%1000000]].size();++i)
			if (!trec[a[coada[p%1000000]][i].fi]||(cost[a[coada[p%1000000]][i].fi]>cost[coada[p%1000000]]+a[coada[p%1000000]][i].se))
			{
				++trec[a[coada[p%1000000]][i].fi];
				if(trec[a[coada[p%1000000]][i].fi]==n)
				{
					k=1;
					break;
				}
				cost[a[coada[p%1000000]][i].fi]=cost[coada[p%1000000]]+a[coada[p%1000000]][i].se;
				if (!marc[a[coada[p%1000000]][i].fi])
				{
					marc[a[coada[p%1000000]][i].fi]=1;
					if (r>1000000)
						r=0;
					coada[++r]=a[coada[p%1000000]][i].fi;
				}
			}
	}
}


int main()
{
	freopen ("bellmanford.in","r",stdin);
	freopen ("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x].push_back(make_pair(y,z));
	}
	bfs();
	if (k)
		printf("Ciclu negativ!");
	else
		for (int i=2;i<=n;++i)
			printf("%d ",cost[i]);
	return 0;
}