#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 50001
#define MMAX 250001
#define INF 1000000000
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,cost[NMAX],val,B[NMAX],C[NMAX];
vector < pair<int,int> > v[NMAX];
queue <int> Q;
struct muchie
{
	int a,b,c;
};
muchie A[MMAX];
char in[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=n; i++)
		cost[i]=INF;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		A[i].a=x;A[i].b=y;A[i].c=z;
		B[y]++;
		v[x].pb(mp(y,z));
	}
}
void solve()
{
	cost[1]=0;
	int i,x,x1,y1;
	Q.push(1);
	while (!Q.empty())
	{
		x=Q.front();
		in[x]=0;
		Q.pop();
		for (i=0; i<v[x].size(); i++)
		{
			x1=v[x][i].f;
			y1=v[x][i].s;
			if (cost[x1]>cost[x]+y1 && C[x1]<=n)
			{
				C[x1]++;
				cost[x1]=cost[x]+y1;
				val++;
				if (!in[x1])
					Q.push(x1),in[x1]=1;
			}
		}
		
	}
}
void show()
{
	int i;
	for (i=1; i<=m; i++)
		if (cost[A[i].a]+A[i].c<cost[A[i].b])
		{
			printf("Ciclu negativ!\n");
			return ;
		}
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]);
	printf("\n");
}
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}