#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int MaxN = 50001;
const int INF = 0x3f3f3f3f;
const char InFile[] = "bellmaford.in";
const char OutFile[] = "bellmaford.out";

int n,m,d[MaxN];
int viz[MaxN];
vector< pair<int,int> > G[MaxN];
queue<int> Q;

int Bellman_Ford()
{
	int nod;
	vector< pair<int,int> >::iterator it,iend;
	for( nod = 1 ; nod <= n ; nod++ )
		d[nod] = INF;
	d[1] = 0;
	Q.push(1);
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			iend = G[nod].end();
			for( it = G[nod].begin() ; it != iend ; ++it )
				if( d[it -> first] > d[nod] + it -> second )
					{
						d[it->first] = d[nod] + it -> second;
						Q.push(it-> first);
						viz[it->first]++;
						if( viz[it->first] > n )
							return 0;
					}
		}
	return 1;
}

int main()
{
	ifstream fin (InFile);
	ofstream fout (OutFile);
	fin >> n >> m;
	int a,b,c;
	for( int i = 0 ; i < m ; i++ )
		{
			fin >> a >> b >> c;
			G[a].push_back(make_pair(b,c));
		}
	fin.close();
	if( Bellman_Ford() )
		{
			for( int i = 2 ; i <= n ; i++ )
				fout << d[i] << ' ';
			fout << '\n';
		}
		else
		fout << "Ciclu negativ!";
	fout.close();
	return 0;
}