#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int Nmax = 50010;
const int inf = 0x3f3f3f3f;

int N,M;
vector < pair<int,int> > L[Nmax];
int sol[Nmax],cnt[Nmax];
int f[Nmax];

void solve()
{
	int current;
	queue<int> q;
	vector< pair<int,int> >::iterator it;

	for(int i=1;i<=N;++i)
		sol[i] = inf;
	sol[1] = 0;

	q.push(1);
	f[1] ++;

	while (!q.empty())
	{
		current = q.front();
		q.pop();
		f[current] --;

		for(it = L[current].begin(); it != L[current].end() ; ++it)
			if (sol[ (*it).first ] > sol[current] + (*it).second)
			{
				sol[ (*it).first ] = sol[current] + (*it).second;
				if (!f[ (*it).first ])
				{
					q.push( (*it).first );
					f[ (*it).first ] = 1;
				}

				cnt[ (*it).first ] ++;
				if (cnt[ (*it).first ] == N)
				{
					printf("Ciclu negativ!\n"); 
					return ;
				}
			}
	}

	for(int i=2;i<=N;++i)
		printf("%d ",sol[i]);
	printf("\n");
}

void read()
{
	int a,b,c;
	scanf("%d",&N);
	scanf("%d",&M);
	for(int i=1;i<=M;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		L[a].push_back( make_pair(b,c) );
	}
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	solve();
	return 0;
}