//relaxeaza graful
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define MAXN 50010
#define INF 0x3f3f3f3f

int N, M;    // N = nr de noduri, M = nr de muchii

vector < pair <int, int> > G[MAXN];    //graful, memorat ca muchii
int d[MAXN];    //d[i] = distanta de la sursa pana la nodul i
int cnt[MAXN];  //cnt[i] = de cate ori a fost nodul i in coada
bool neg_cycle; //true daca exista ciclu negativ

void Read();
void BellmanFord(int );
void Write();

int main()
{
	Read();
	BellmanFord ( 1 );
	
	Write();
	return 0;
}

void Read()
{
	ifstream fin("bellmanford.in");
	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();
}

void BellmanFord ( int sursa )
{
	bool InQueue[MAXN], neg_cicyle;
	queue <int> Q;
	
	memset ( d, INF, sizeof(d) );
	memset ( InQueue, false, sizeof (InQueue) );
	
	d[sursa] = 0;
	Q.push(sursa);
	InQueue[sursa] = true;
	
	while ( !Q.empty() )
	{
		int p = Q.front();
		Q.pop();
		InQueue[p] = false;
		
		for ( vector <pair <int, int> >::iterator it = G[p].begin(); it != G[p].end(); ++it )    //pentru fiecare muchie din graf
			if ( d[p] + it->second < d[it->first] )
			{
				d[it->first] = d[p] + it->second;
				if ( !InQueue[it->first] )
				{
					if ( cnt[it->first] > N )
					{
						neg_cycle = true;
						return;
					}
					InQueue[it->first] = true;
					Q.push ( it->first );
					++cnt[it->first];
				}
			}
	}
	
}

void Write()
{
	ofstream fout("bellmanford.out");
	
	if ( !neg_cycle )
		for ( int i = 2; i <= N; ++i )
			fout << d[i] << ' ';
	else
		fout << "Ciclu negativ!" << '\n';
	fout.close();
}