#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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 BellmanFord(int node);
void Read();


int main()
{
	Read();
	BellmanFord(1);
	if ( check )
		os << "Ciclu negativ!";
	else
		for ( int i = 2; i <= n; ++i )
			os << D[i] << ' ';
	is.close();
	os.close();
	return 0;
}


void BellmanFord(int node)
{
	int x, cost;
	D[node] = 0;
	v = 1;
	Q.push({node, 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 + g.second )
				{
					v[g.first] = true;
					cnt[g.first]++;
					D[g.first] = cost + g.second;
					Q.push({g.first, D[g.first]});
				}
				else
					if ( v[g.first] && D[g.first] > cost + g.second )
					{
						D[g.first] = cost + g.second;
						cnt[g.first]++;
						if ( cnt[g.first] == n )
							check = true;
					}
	}
}

void Read()
{
	is >> n >> m;
	G = vector<vector<pair<int, 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});
    }
}