#include <stdio.h>
#include <queue>
using namespace std;
#define INF 1000000000
int n,m,i,dis[50001],x,y,z,este[50001],cate[50001],ok;
struct nod{int y; int c; nod *next;};
nod *G[50001];
queue <int> q;
int add(int a,int b,int c)
{
	nod *nou=new nod;
	nou->y=b;
	nou->c=c;
	nou->next=G[a];
	G[a]=nou;
	return 0;
}
int main(void)
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	for (i=2;i<=n;i++)
		dis[i]=INF;
	dis[1]=0;
	q.push(1);
	ok=1;
	while (!q.empty() && ok)
	{
		int x=q.front();
		este[x]=0;
		q.pop();
		nod *nou=new nod;
		nou=G[x];
		while (nou)
		{
			int y=nou->y,c=nou->c;
			if (dis[y]>dis[x]+c)
			{
				dis[y]=dis[x]+c;
				if (!este[y])
				{
					if (cate[y]>n)
						ok=0;
					else
					{
					este[y]=1;
					q.push(y);
					cate[y]++;
					}
				}
				
			}
			nou=nou->next;
		}
	}
	if (!ok)
		printf("Ciclu negativ!\n");
	else
	{
		for (i=2;i<=n;i++)
			printf("%d ",dis[i]);
		printf("\n");
	}
	return 0;
}