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

#define input "bellmanford.in"
#define output "bellmanford.out"
#define NMAX 50005
#define SABATON 100000000

using namespace std;

ifstream in(input);
ofstream out(output);

struct m
{
	int dest, cost;
};
struct a
{
	int s, d, c;
};
vector < m > muchii[NMAX];
vector < a > muchii_t;
int N, M, dist[NMAX], frecv[NMAX];
bool uz[NMAX];

class Meth
{
	public:
	bool operator () (int a, int b)
	{
		return dist[a] < dist[b];
	}
}; 
queue < int > coada;

void Read_Data()
{
	in >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		muchii[x].push_back({ y, c });
		muchii_t.push_back({ x, y, c });
	}
}

void Define_Dist()
{
	for (int i = 2; i <= N; i++)
		dist[i] = SABATON;
}

void Bellman_Ford()
{
	int operations = 0;
	bool valid = true;
	coada.push(1);
	uz[1] = 1;
	frecv[1] = 1;
	while (!coada.empty() && valid)
	{
		int nod = coada.front();
		int cost = dist[nod];
		coada.pop();
		uz[nod] = 0;
		for (unsigned i = 0; i < muchii[nod].size(); i++)
		{
			int new_nod = muchii[nod][i].dest;
			int new_cost = muchii[nod][i].cost;
			if (dist[new_nod] > cost + new_cost)
			{
				dist[new_nod] = cost + new_cost;
				if (!uz[new_nod])
				{
					frecv[new_nod]++;
					if (frecv[new_nod] > N)
						valid = false;
					coada.push(new_nod);
					uz[new_nod] = 1;
				}
			}
		}
	}
}

void Check_Negative_Route()
{
	for (unsigned i = 0; i < muchii_t.size(); i++)
	{
		int nod = muchii_t[i].s;
		int new_nod = muchii_t[i].d;
		int cost = muchii_t[i].c;
		if (dist[new_nod] > dist[nod] + cost)
		{
			out << "Ciclu negativ!\n";
			return;
		}
	}
	for (int i = 2; i <= N; i++)
	{
		out << dist[i] << " ";
	}
}

int main()
{
	Read_Data();
	Define_Dist();
	Bellman_Ford();
	Check_Negative_Route();
	return 0;
}