#include<fstream>
#define M 2000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
unsigned short q[800000],nr[50001];
int cost[50001],n,m;
bool viz[50001];
struct nod
{
	int inf;
	short c;
	nod* leg;
};
typedef nod* PNod;
PNod L[50001];
void add(int x,int y,int z)
{
	PNod p=new nod;
	p->inf=y;
	p->c=z;
	p->leg=L[x];
	L[x]=p;
}
void bell(int poz)
{
	int i;
	int inc=1,sf=1;
	q[inc]=poz;
	for(i=1;i<=n;i++)
		cost[i]=M;
	cost[poz]=0;nr[1]++;
	while(inc<=sf)
	{
		viz[q[inc]]=0;
		for(PNod p=L[q[inc]];p;p=p->leg)
		{
			if(cost[q[inc]]+p->c<cost[p->inf])
			{
				cost[p->inf]=cost[q[inc]]+p->c;
				nr[p->inf]++;
				if(!viz[p->inf])
				{
					viz[p->inf]=true;
					sf++;
					q[sf]=p->inf;
					if(nr[p->inf]>n)
					{
						g<<"Ciclu negativ!";
						return;
					}
				}
			}
		}
		
		inc++;		
	}
	for(i=2;i<=n;i++)
		g<<cost[i]<<" ";
	
}
int main()
{
	int a,b,costi,i;
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		f>>a>>b>>costi;
		add(a,b,costi);
	}
	bell(1);
	return 0;
}