#include<stdio.h>
#include<vector>
#include<deque>
#include<utility>
using namespace std;
vector<pair<int,int> > v[50001];
deque<int> Q;
int n,m,i,o,d,c,N,C,V,cst,q[50001],cnt[50001],cost[50001],oo=1000000000;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.our","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&o,&d,&c);
		v[o].push_back(make_pair(d,c));
	}
}
void solve()
{
	vector<pair<int,int> >::iterator it;
	for(i=2;i<=n;i++)cost[i]=oo;
	Q.push_back(1);q[1]=1;cnt[1]++;
	while(!Q.empty())
	{
		N=Q.front();C=cost[N];
		for(it=v[N].begin();it!=v[N].end();it++)
		{
			V=it->first;
			cst=C+it->second;
			if(cst<cost[V])
			{
				cost[V]=cst;
				if(!q[V])
				{
					if(cnt[V]>n){printf("Ciclu negativ!\n");return;}
					cnt[V]++;q[V]=1;
					Q.push_back(V);
				}
			}
		}
		Q.pop_front();
		q[N]=0;
	}
	for(i=2;i<=n;i++)printf("%d ",cost[i]);
}