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

#define MAXN 250
#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

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

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

void Read()
{
	ifstream fin("graf.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];
	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] )
				{
					InQueue[it->first] = true;
					Q.push ( it->first );
				}
			}
	}
	
}

bool CicluNegativ()
{
	for ( int i = 2; i <= N; ++i )
		for ( vector < pair <int, int> >::iterator it = G[i].begin(); it != G[i].end(); ++i )
			if ( d[i] + it->second < d[it->first] )
				return true;
	return false;
}

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