#include<cstdio>
#include<utility>
#include<vector>
#include<deque>
#include<bitset>
#define NV it->first
#define DV it->second
using namespace std;
bitset<50002> q;
vector<pair<int,int> > v[50002];
deque<int> Q;
void read(),solve();
int n,L,D,N,cnt[50002],d[50002],oo=1<<30,i;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	int x,y,c,m;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&x,&y,&c);
		v[x].push_back(make_pair(y,c));
	}
}
void solve()
{
	vector<pair<int,int> >::iterator it;
	for(i=2;i<=n;i++)d[i]=oo;
	Q.push_back(1);d[1]=0;q[1]=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(!q[it->first])
				{
					q[it->first]=1;cnt[it->first]++;
					if(cnt[it->first]>n)
					{
						printf("Ciclu negativ!\n");
						return;
					}
					Q.push_back(it->first);
				}
				d[it->first]=d[Q.front()]+it->second;
			}
		q[Q.front()]=0;
		Q.pop_front(); 
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]); 
}