#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1000000000
#define pb push_back
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,D[NMAX],B[NMAX];
vector <pii> A[NMAX];
queue <int> Q;
char in[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		A[x].pb(mp(y,z));
	}
}
void init()
{
	int i;
	for (i=2; i<=n; i++)
		D[i]=INF;
}
void solve()
{
	init();
	Q.push(1); in[1]=1;
	int i,nod,vec,cost;
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop(); in[nod]=0;
		for (i=0; i<A[nod].size(); i++)
		{
			vec=A[nod][i].f; cost=A[nod][i].s;
			if (D[vec]>D[nod]+cost)
			{
				D[vec]=D[nod]+cost;
				if (!in[vec])
					Q.push(vec),in[vec]=1,B[vec]++;
				if (B[vec]==n)
				{
					printf("Ciclu negativ!\n");
					exit(0);
				}
			}
		}
	}
	
	for (i=2; i<=n; i++)
		printf("%d ",D[i]);
}
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	solve();
	return 0;
}