#include<fstream.h>
#define u (1<<30)
int d[50100],ver[251000],leg[251000],start[50100],c[50100],cc[50100],pus[50100],cost[251000];
int main()
{
	int i,m,n,nr=0,x,y,t;
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		ver[i]=y;
		leg[i]=start[x];
		start[x]=i;
		f>>cost[i];
	}
	for(i=2;i<=n;i++)
		d[i]=u;
	c[++c[0]]=1;
	while(c[0]&&nr<=n)
	{
		nr++;
		for(i=1;i<=c[0];i++)
		{
			t=start[c[i]];
			while(t)
			{
				if(d[ver[t]]>d[c[i]]+cost[t])
				{
					d[ver[t]]=d[c[i]]+cost[t];
					if(!pus[ver[t]])
					{
						cc[++cc[0]]=ver[t];
						pus[ver[t]]=1;
					}
				}
				t=leg[t];
			}
		}
		for(i=1;i<=cc[0];i++)
		{
			c[i]=cc[i];
			pus[c[i]]=0;
		}
		c[0]=cc[0];
		cc[0]=0;
	}
	if(nr==n+1)
		g<<"Ciclu negativ!";
	else
		for(i=2;i<=n;i++)
			g<<d[i]<<' ';
	return 0;
}