#include <bits/stdc++.h>
#define NMAX 50009
#define INF 9999999
#define int long long int
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int, int> >g[NMAX];
int uz[NMAX];
int d[NMAX];
int n, m;
class compar
{
public:
	bool operator ()(int x, int y)
	{
		return d[x] > d[y];
	}
};

priority_queue<int, vector<int>, compar> H;
void citire();
void bellman();
int32_t main()
{
	citire();
	bellman();
	return 0;
}
void citire()
{
	int i;
	int x, y;
	int cost;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> cost;
		g[x].push_back( { y,cost } );

	}
}

void bellman()
{
	int i;
	for (i = 0; i < NMAX; i++)
		d[i] = INF;
	H.push(1);
	uz[1] = 1;
	d[1] = 0;
	while (!H.empty())
	{
		int act = H.top();
		H.pop();
		uz[act]++;
		if (uz[act] > n)
			{fout << "Ciclu negativ!"; return;
			}
		for (i = 0; i < g[act].size(); i++)
		{
			int vec = g[act][i].first;
			int cost = g[act][i].second;
			if (d[vec] > d[act] + cost)
			{
				d[vec] = d[act] + cost;
				H.push(vec);

			}
		}
	}
	for (i = 2; i <= n; i++)
		fout << d[i] << " ";
}