#include<fstream>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
const char* INFILE="bellmanford.in";
const char* OUTFILE="bellmanford.out";

int n,m;
int dist[MAXN];
struct edge
{
	int dest,cost;
	void set(int v,int w)
	{
		dest=v;
		cost=w;
	}
};
vector<edge> adj[MAXN];


void read()
{
	edge aux;
	int u,v,w;
	ifstream fin(INFILE);
	fin>>n>>m;
	for (int i=1; i<=m; ++i)
	{
		fin>>u>>v>>w;
		aux.set(v,w);
		adj[u].push_back(aux);
	}
	fin.close();
}
void relax(int u,int v,int w)
{
	if (dist[u]+w<dist[v])
		dist[v]=dist[u]+w;
}
bool bellmanford()
{
	/* INITIALIZARE */

	for (int i=1; i<=n; ++i)
		dist[i]=INF;
	dist[1]=0;
	/* RELAXARE */
	for (int u=1; u<=n; ++u)
	{
		for (vector<edge>::iterator p=adj[u].begin(); p!=adj[u].end(); ++p)
		{
			relax(u,(*p).dest,(*p).cost);
		}
	}

	for (int u=1; u<=n; ++u)
	{
		for (vector<edge>::iterator p=adj[u].begin(); p!=adj[u].end(); ++p)
		{
			if (dist[u]+(*p).cost<dist[(*p).dest])
				return false;
		}
	}
	return true;

}
void write(bool ok)
{
	ofstream fout(OUTFILE);
	if (ok)
	{
		for (int i=2; i<=n; ++i)
			fout<<dist[i]<<' ';
		fout<<'\n';
	}
	else
		fout<<"Ciclu negativ!\n";
	fout.close();
}

int main()
{
	read();
	write(bellmanford());
	return 0;
}