#include<stdio.h>
#include<vector>

using namespace std;
#define Nmax 50010
#define mod 100010
#define inf 0x3f3f3f3f

int N,M,d[Nmax],v[Nmax],cnt[Nmax];
vector < pair<int,int> > l[Nmax];
int c[mod];

int Bellman()
{
	for(int i=1;i<=N;++i)
		d[i]=inf;
	int st,dr,nod,leg;
	c[1]=1;
	d[1]=0;
	v[1]=1;
	
	for(st=dr=1 ; st<=dr ;++st)
		for(int i=0;i<(int)l[ c[st%mod] ].size() ;++i)
		{
			nod=c[st%mod];
			leg=l[c[st%mod]][i].first;
			if (d[ leg ] > d[ nod ] + l[c[st%mod]][i].second)
			{
				d[ leg ] = d[ nod ] + l[c[st%mod]][i].second;
				cnt[leg]++;
				if (v[ leg ]<st)
				{
					v[ leg ]=++dr;
					c[dr%mod]=leg;
				}
			}
			if (cnt[leg]==N)
				return 0;
		}
	return 1;
}

void solve()
{
	if (!Bellman())
	{
		printf("Ciclu negativ!\n");
		return ;
	}
	
	for(int i=2;i<=N;++i)
		printf("%d ",d[i]);
	printf("\n");
}

void cit();

int main()
{
	cit();
	solve();
	return 0;
}

void cit()
{
	int a,b,x;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;++i)
	{
		scanf("%d%d%d",&a,&b,&x);
		l[a].push_back( make_pair(b,x));
	}
}