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

using namespace std;

#define NMAX 50001
#define INF 50000100
int z[NMAX],qq,d[NMAX],b,c,in,sf,i,j,n,m,k,l,a,s;
vector<int> x[NMAX], y[NMAX];
queue<int> q;
char ss[32];
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
//	scanf("%d%d",&n,&m);
	scanf("%d%d%c",&n,&m,&c);

	for (i=1;i<=m;i++)
	{
		fgets(ss,32,stdin);
		l=strlen(ss)-1;
		a=b=c=j=0;
		while (ss[j]!=' ')
			a=a*10+ss[j++]-48;

		j++;
		while (ss[j]!=' ')
			b=b*10+ss[j++]-48;

		j++;
		qq=0;
		while (j<l)
		{
			if (ss[j]=='-')
			{
				qq=1;
				j++;
			}
			c=c*10+ss[j++]-48;
		}
		if (qq)
			c=0-c;

//		scanf("%d%d%d",&a,&b,&c);
		x[a].push_back(c);
		y[a].push_back(b);
	}
	q.push(1);
	for (i=2;i<=n;i++)
		d[i]=INF;
	z[1] = 1;
	while (!q.empty())
	{
		int nod = q.front(); q.pop();

		for (i=0;i<(int)y[nod].size();i++)
			if (d[nod]+x[nod][i]<d[y[nod][i]])
			{
				d[y[nod][i]]=d[nod]+x[nod][i];
				if (!z[y[nod][i]])
				{
					q.push(y[nod][i]);
					z[y[nod][i]]=1;
				}
			}
		z[nod]=0;
	}
	for (int nod=1;nod<=n;nod++)
	for (i=0;i<(int)y[nod].size();i++)
		if (d[nod]+x[nod][i]<d[y[nod][i]])
		{
			printf("Ciclu negativ!");
			return 0;
		}

	for (i=2;i<=n;i++)
		if (d[i]!=INF)
			printf("%d ",d[i]);
		else{
			printf("0 ");
			d[i] = 0;
		}
	printf("\n");

	/*fclose(stdin);
	fclose(stdout);
	
	freopen("ccp.txt", "rt", stdin);
	freopen("kkt.out", "w",stdout);
	int www[100000], vf;
	for (i = 2; i <= n; i ++){
		scanf("%d", &vf);
		if (vf != d[i])
			printf("%d %d %d\n", i, vf, d[i]);
	}
	*/
	return 0;
}