#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <utility>
#include <stack>
#include <set>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int N = 50001;
int n, m, s;
vector<pair<int, int>> adj[N];
int d[N], tata[N];
vector<int> ciclu;

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int u, v, c;
		fin >> u >> v >> c;
		adj[u].push_back({v, c});
	}
	for (int i = 1; i <= n; ++i)
	{
		d[i] = INT_MAX;
	}
	s = 1;
	d[s] = 0;
	int v_neg;
	for (int i = 1; i <= n; ++i)
	{
		v_neg = -1;
		for (int u = 1; u <= n; ++u)
		{
			if (d[u] == INT_MAX)
			{
				continue;
			}
			for (auto [v, cv] : adj[u])
			{
				if (d[u] + cv < d[v])
				{
					d[v] = d[u] + cv;
					tata[v] = u;
					v_neg = v;
				}
			}
		}
	}
	if (v_neg != -1)
	{
		fout << "Ciclu negativ!\n";
	}
	/*
		for (int i = 1; i <= n; ++i)
		{
			v_neg = tata[v_neg];
		}
		int nod = v_neg;
		do
		{
			ciclu.push_back(v_neg);
			v_neg = tata[v_neg];
		} while (v_neg != nod);
		fout << "Circuit de cost negativ:\n";
		for (auto u : ciclu)
		{
			fout << u << ' ';
		}
		fout << '\n';
	}
	*/
	else
	{
		for (int i = 1; i <= n-1; ++i)
		{
			/*
			if (i == s)
			{
				continue;
			}
			int j = i;
			stack<int> cale;
			while (j != 0)
			{
				cale.push(j);
				j = tata[j];
			}
			while (!cale.empty())
			{
				fout << cale.top() << ' ';
				cale.pop();
			}
			*/
			fout  << d[i+1] << ' ';
		}
		fout << '\n';
	}
	fin.close();
	fout.close();
	return 0;
}