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

using namespace std;

vector <int> graph[100005];
vector <int> graphC[100005];
int viz[100005];
int dist[100005];

int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int n, m;
	f >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		graphC[a].push_back(c);
	}
	for (int i = 2; i <= n; i++)
		dist[i] = 1000000;
	bool ok = true;
	queue <int> q;
	q.push(1);
	while (!q.empty() && ok)
	{
		int best = q.front();
		q.pop();
		if (viz[best] > n - 1)
		{
			ok = false;
		}
		viz[best]++;
		if (ok)
		{
			int lim = graph[best].size();
			for (int i = 0; i < lim; i++)
			{
				int vecin = graph[best][i];
				int cost = graphC[best][i];
				if (dist[best] + cost < dist[vecin])
				{
					dist[vecin] = dist[best] + cost;
					q.push(vecin);
				}
			}
		}
	}
	if (ok)
		for (int i = 2; i <= n; i++)
			g << dist[i] << " ";
	else
		g << "Ciclu negativ!";
	return 0;
}