#include<fstream>

#define nmax 20000
#define inf 1<<30

using namespace std;


int a[nmax][nmax],n,m,d[nmax],t[nmax];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");





void citire()
{
	int i,j,x,y,z;
	f>>n>>m;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=inf;
	
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		a[x][y]=z;
	}
	
}

void bellmanford(int x)
{
	int i,ok,j,k;
	
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		
		
	}
	d[x]=0;
	
	
	for(i=1;i<=n;i++)
	{
		ok=0;
		
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if(d[j]!=inf&&a[j][k]!=inf)
					if(d[k]>d[j]+a[j][k])
					{
						d[k]=d[j]+a[j][k];
						t[k]=j;
						ok=1;
					}
				
		
	}
	
	if(ok) g<<"Ciclu negativ!";
		
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	
	
}


int main()
{
	
	citire();
	bellmanford(1);
	
	
	
return 0;
}