#include<cstdio>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
int n,m;
int dist[MAXN],pred[MAXN];
struct edge{int dest,cost;};
vector<edge> adj[MAXN];
void read()
{
	int x,y,c;
	edge aux;
	freopen("bellmanford.in","r",stdin);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		aux.cost=c;
		aux.dest=y;
		adj[x].push_back(aux);
	}
}
int bellmanford()
{
	int i;
	for (i=1; i<=n; ++i)
	{
		if (i==1)
			dist[i]=0;
		else
			dist[i]=INF;
		pred[i]=0;
	}
	
	for (i=1; i<=n; ++i)
	{
		for (vector<edge>::iterator it=adj[i].begin(); it!=adj[i].end(); ++it)
		{
			if (dist[i]+(*it).cost<dist[(*it).dest])
			{
				dist[(*it).dest]=dist[i]+(*it).cost;
				pred[(*it).dest]=i;
			}
		}
	}
	for (i=1; i<=n; ++i)
	{
		for (vector<edge>::iterator it=adj[i].begin(); it!=adj[i].end(); ++it)
		{
			if (dist[i]+(*it).cost<dist[(*it).dest])
			{
				return 0;
			}
		}
	}
	return 1;
}
void write()
{
	freopen("bellmanford.out","w",stdout);
	int rez=bellmanford();
	if (!rez)
	{
		printf("Ciclu negativ!\n");
	}
	else
	{
		for (int i=2; i<=n; ++i)
			printf("%d ",dist[i]);
		printf("\n");
	}
}
int main()
{
	read();
	write();
	return 0;
}