#include<cstdio>
#include<vector>
#include<utility>
#include<bitset>
#include<deque>
using namespace std;

int n,m,x,y,c,i,oo=1<<30,d[50010],cnt[50010];
vector<pair<int,int> > V[50010];
deque<int> Q;
bitset<50010> 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(;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);q[1]=1;
	for(;Q.size();)
	{
		x=Q.front();
		for(it=V[x].begin();it!=V[x].end();it++)
		{
			y=it->first;
			c=it->second;
			if(d[x]+c<d[y])
			{
				if(!q[y])
				{
					q[y]=1;cnt[y]++;
					if(cnt[y]>n){printf("Ciclu negativ!");return;}
					Q.push_back(y);
				}
				d[y]=d[x]+c;
			}
		}
		Q.pop_front();
		q[x]=0;
	}
	for(i=2;i<=n;i++)printf("%d ",d[i]);
}