#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define N 50005
#define INF 2000000000

using namespace std;

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

vector<pair<int, int> > graf[N];
queue<int> q;
int viz[N];
int a[N], fv[N];
int n, m;


void Citire()
{
	int i, x, y, z;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> z;
		graf[x].push_back({ y,z });
	}
}


void Bellmanford(int sursa)
{
	int i, vecin, cost;
	for (i = 1; i <= n; i++)
		a[i] = INF;
	a[sursa] = 0;
	q.push(sursa);
	while (!q.empty())
	{
		int coada = q.front();
		viz[coada] = 0;
		for (int i = 0; i < graf[coada].size(); i++)
		{
			vecin = graf[coada][i].first;
		    cost = graf[coada][i].second;
			if (a[vecin] > a[coada] + cost)
			{
				a[vecin] = a[coada] + cost;
				if (viz[vecin] == 0)
				{
					viz[vecin] = 1;
					fv[vecin]++;
					q.push(vecin);
					if (fv[vecin] == n)
					{
						fout << "Ciclu negativ!";
						return;
					}
				}
			}
		}
		q.pop();
	}
	for (int i = 2; i <= n; i++)
		fout << a[i] << " ";
}


int main()
{
	Citire();
	Bellmanford(1);
	return 0;
}