#include<fstream.h>
#include<queue>
#define inf 1000000000
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int i,j,n,m,a[1000][1000],x,y,d[10001],viz[1001],k,z,nr[10001];
queue<int> q;
int main ()
{
 f>>n>>m;
 for(i=1;i<=n;i++){
	 d[i]=inf;
	for(j=1;j<=m;j++)
		a[i][j]=inf;
 }
 for(i=1;i<=m;i++)
    {f>>x>>y>>z;
     a[x][y]=z;
	} 
 d[1]=0;
 q.push(1);
 nr[1]=1;
 viz[1]=1;
 while(!q.empty()){
	k=(int)q.front();
	for(i=1;i<=n;i++)
		if(a[k][i]!=inf && d[i]>d[k]+a[k][i]){
			d[i]=d[k]+a[k][i];
			nr[i]++;
			if(nr[i]>=n){
				g<<"Ciclu negativ!";
				return 0;
			}
			if(viz[i]==0)
			{viz[i]=1;
			 q.push(i);
			} 
		}
	viz[k]=0;
    q.pop();
    }
 for(i=2;i<=n;i++)
	g<<d[i]<<' ';
 return 0;
}