#include<fstream.h>
#include<iostream.h>

const int inf=1<<30;
int n,m,x,i,j,d[50001],c[50001],li=1,ls=1;

struct nod {
		   int y,c;
		   nod *next;
		   }*p,*v[50001];

int main()
{
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

fin>>n>>m;
for(i=1;i<=m;i++){
				 p=new nod;
				 fin>>x>>p->y>>p->c;
				 p->next=v[x];
				 v[x]=p;
				 }

for(i=2;i<=n;i++)d[i]=inf;
c[1]=1;

for(i=1;i<n;i++)	
   {
   for(j=li;j<=ls;j++)
				   {
					p=v[c[j]];
					while(p){
							if(d[p->y]>d[c[j]]+p->c){
												 d[p->y]=d[c[j]]+p->c;
												 c[++ls]=p->y;
												 }
							p=p->next;
							}
					}
   li++;
   }
for(j=1;j<=n;j++)
				   {
					p=v[j];
					while(p){
							if(d[p->y]>d[j]+p->c){
												 fout<<"Ciclu negativ!";
												 return 0;
												 }
							p=p->next;
							}
					}

for(i=2;i<=n;i++)fout<<d[i]<<' ';
return 0;
}