#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
struct edge{int dest,cost;};
int n,m;
int dist[MAXN];
queue<int> q;
vector<edge> adj[MAXN];
bitset<MAXN> uz;

void read()
{
	ifstream fin("bellmanford.in");
	fin>>n>>m;

	edge aux;
	int x,y,c;
	for (int k=1; k<=m; ++k)
	{
		fin>>x>>y>>c;
		aux.dest=y;
		aux.cost=c;
		adj[x].push_back(aux);
	}
	fin.close();
}
bool bellman_ford()
{
	int i;
	for (i=2; i<=n; dist[i]=INF, ++i);
	for (i=1; i<=n-1; ++i)
	{
		for (i=1; i<=n; uz[i]=false, ++i);
		q.push(1);
		while (!q.empty())
		{
			int aux=q.front();
			for (vector<edge>::iterator k=adj[aux].begin(); k!=adj[aux].end(); ++k)
			{
				if (dist[k->dest]>dist[aux]+k->cost && !uz[k->dest])
				{
					dist[k->dest]=dist[aux]+k->cost;
					q.push(k->dest);
					uz[k->dest]=true;
				}
			}
			q.pop();
		}
	}
	for (i=1; i<=n; ++i)
	{
		for (vector<edge>::iterator k=adj[i].begin(); k!=adj[i].end(); ++k)
		{
			if (dist[k->dest]>dist[i]+k->cost)
				return false;
		}
	}
	return true;
}
void write()
{
	ofstream fout("bellmanford.out");
	bool rez=bellman_ford();
	if (!rez)
		fout<<"Ciclu negativ!";
	else
		for (int i=2; i<=n; fout<<dist[i]<<' ', ++i);
	fout<<'\n';
	fout.close();
}
int main()
{
	read();
	write();
	return 0;
}