// infoarena: problema/bellmanford //
#include <fstream>
using namespace std;

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

const int MAXM = 250010;
const int MAXN = 50010;

int n,m,i,j,k,e[MAXM][3],d[MAXN],nod,muchie,c,ok;

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
		in>>e[i][0]>>e[i][1]>>e[i][2];
	
	for(i=2; i<=n; i++)
		d[i] = 1<<29;
	
	for(nod=2; nod<=n; nod++)
	{
		ok = 0;
		for(muchie=1; muchie<=m; muchie++)
		{
			i = e[muchie][0];
			j = e[muchie][1];
			c = e[muchie][2];
			if(d[j] > d[i] + c)
				d[j] = d[i] + c, ok = 1;
		}
		for(muchie=1; muchie<=m; muchie++)
		{
			i = e[muchie][0];
			j = e[muchie][1];
			c = e[muchie][2];
			if(d[j] > d[i] + c)
			{
				out<<"Ciclu negativ!";
				return 0;
			}
		}
		if(!ok)
			break;
	}
	
	for(i=2; i<=n; i++)
		out<<d[i]<<' ';
	
	return 0;
}