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

using namespace std;

#define NMAX 50001
#define INF 50000100
int z[NMAX],d[NMAX],b,c,in,sf,i,j,n,m,k,l,a,s;
vector<int> x[NMAX], y[NMAX];
queue<int> q;

int main()
{
	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",&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 (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;
}