#include <fstream>
using namespace std;

int n,m,i,nr,x[50100],y[50100],c[50100],d[50100];

int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	
	f>>n; f>>m;
	for (i=1;i<=m;i++)
	{
		 f>>x[i];
		 f>>y[i];
		 f>>c[i];
		 if (x[i]==1)
			 d[y[i]]=c[i];
	}
	
	for (i=2;i<=n;i++)
		 if (d[i]==0)
			 d[i]=0x3f3f3f3f;
		 
	int ok=0;

	while(ok==0)
	{
		ok=1;
		nr++;
		for (i=1;i<=m;i++)
			 if (d[y[i]]>d[x[i]]+c[i])
			 {
				 d[y[i]]=d[x[i]]+c[i];
				 ok=0;
        }
		if (nr>50000){
			printf("Ciclu negativ!\n");
			return 0;
			
		}
	}
	
	for (i=2;i<=n;i++)
		 g<<d[i]<<" ";
	
	return 0;
	
}