#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 50010
#define INF 1<<20
int n,m,a,b,c,i,D[MAXN],u[MAXN],v[MAXN],bmf(int);
vector<pair<int,int> > G[MAXN];
queue<int> Q;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	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),G[a].push_back(make_pair(b,c));
}
void solve()
{
	if(!bmf(1))
		printf("Ciclu negativ!\n");
	else
		for(i=2;i<=n;i++)
			printf("%d ",D[i]==INF?0:D[i]);
}
int bmf(int node)
{
	vector<pair<int, int> >::iterator it;
	int c;
	for(i=1;i<=n;i++)D[i]=INF;
	Q.push(node);D[node]=0;u[node]=1;v[node]=1;
	while(!Q.empty())
	{
		c = Q.front();
		v[c]=0;
		for(it=G[c].begin();it!=G[c].end();it++)
		{
			node = it->first;
			if(D[node] > it->second+D[c])
			{
				D[node] = it->second+D[c];
				if(!v[node])
				{
					v[node]=1;
					if(u[node]>n) return 0; //avem ciclu negativ
					u[node]++;				
					Q.push(node);
				}
			}
		}
		Q.pop();
	}
	return 1;
}