#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

ifstream is("bellmanford.in");
ofstream os("bellmanford.out");

#define INF 0x3f3f3f3f

vector<vector<pair<int, int> > > G;
vector<int> D;
queue<pair<int, int> > Q;
int n, m;
bitset<50001> v;
int cnt[50001];
bool check;

void Bellman-Ford(int x);
void Read();


int main()
{
	Read();
	Bellman-Ford(1);
	if ( check )
		os << "Ciclu negativ!";
	else
		for ( const int& d : D )
			os << d << ' ';
	is.close();
	os.close();
	return 0;
}


void Bellman-Ford(int x)
{
	int x, cost;
	D[x] = 0;
	v = 1;
	Q.push({x, 0});
	while ( !Q.empty() )
	{
		x = Q.front().first;
		cost = Q.front().second;
		Q.pop();
		for ( int i = 1; i <= n; ++i )
			for ( const auto& g : G[x] )
				if ( !v[g.first] && D[g.first] > cost + D[g.second] )
				{
					v[g.first] = true;
					cnt[g.first]++;
					D[g.first] = cost + D[g.second];
					Q.push({g.first, D[g.first]});
				}
				else
					if ( v[g.first] && D[g.first] > cost + D[g.second] )
					{
						D[g.first] = cost + D[g.second];
						cnt[g.first]++;
						if ( cnt[g.first] == n )
							check = true;>
					}
	}
}

void Read()
{
	is >> n >> m;
	G = vector<vector<int> >(n + 1);
	D = vector<int>(n + 1, INF);
	int x, y, cost;
	for ( int i = 1; i <= n; ++i )
	{
		is >> x >> y >> cost;
		G[x].push_back({y, cost});
}