#include<cstdio>
#include<vector>
#include<deque>
#include<bitset> 

using namespace std;
void read(),solve();
int m,n,i,x,y,z,d[50010],cnt[50010];
bitset<50010> k;
vector<pair<int,int> > v[50010];
deque<int> q;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back(make_pair(y,z));
	}
}
void solve()
{
	vector<pair<int,int> >::iterator it;
	for(i=2;i<=n;i++)
		d[i]=1<<30;
	d[1]=0;q.push_back(1);
	for(;q.size();)
	{
		for(it=v[q.front()].begin();it!=v[q.front()].end();it++)
			if(d[q.front()]+it->second<d[it->first])
			{
				if(!k[it->first])
				{
					cnt[it->first]++;
					k[it->first]=1;
					d[it->first]=d[q.front()]+it->second;
					if(cnt[it->first]>n)
					{
						printf("Ciclu negativ!");
						return;
					}
					q.push_back(it->first);
				}
				d[it->first]=d[q.front()]+it->second;
			}
		k[q.front()]=0;
		q.pop_front();
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
}