#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000000000000

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

struct edge
{
	int node;
	long long cost;
};

void citire();
bool bf();

int n, m, start = 1;
long long d[50005];
int gr[50005], prec[50005], nr[50005];
vector<edge> G[50005];
queue<int> q;

int main()
{
	citire();
	if (bf())
	{
		for (int i = 2; i <= n; i++)
			fout << d[i] << ' ';
		fout << '\n';
	}
	else fout << "Ciclu negativ!\n";
	return 0;
}

bool bf()
{
	q.push(start);
	int x;
	edge y;
	bool ok = true;
	while (!q.empty() && ok)
	{
		x = q.front();
		q.pop();
		for (int i = 0; i < gr[x]; i++)
		{
			y = G[x][i];
			if (d[y.node] > d[x] + y.cost)
			{
				d[y.node] = d[x] + y.cost;
				nr[y.node]++;
				if (nr[y.node] == n)
				{
					ok = false;
					break;
				}
				q.push(y.node);
			}
		}
	}

	return ok;
}

void citire()
{
	int x;
	edge e;

	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> x >> e.node >> e.cost;
		++gr[x];
		G[x].push_back(e);
	}
	for (int i = 1; i <= n; i++)
	{
		nr[i] = 0;
		d[i] = (i == 1 ? 0 : INF);
	}
}