#include<fstream>
#include<queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,cost[50005],pas,a,b,c,w,y,apar[50005];
struct nod
{ int nr;
  int c;
  nod *urm;
} *v[50005],*p;
queue<int> q;
char prez[50005];
int bmf()
{ while(!q.empty())
		{ w=q.front();
		  q.pop();
		  prez[w]='\0';
		  p=v[w];
		  while(p)
			  { if(cost[p->nr]>cost[w]+p->c)
				  { cost[p->nr]=cost[w]+p->c;
				    if(!prez[p->nr]) {q.push(p->nr),prez[p->nr]='1',++apar[p->nr];if(apar[p->nr]>n) return 0;}
				  }
				p=p->urm;
			  }
		}
  return 1;
}

int main()
{
	int i;
	f>>n>>m;
	for(i=0;i<m;++i)
		{ f>>a>>b>>c;
		  p=new nod;
		  p->nr=b;
		  p->c=c;
		  p->urm=v[a];
		  v[a]=p;
		}
	for(i=2;i<=n;i++) cost[i]=INT_MAX;
	q.push(1);
	//pas=1;
	y=n*n;
	
	if(bmf()) for(i=2;i<=n;i++) g<<((cost[i]<INT_MAX) ? cost[i] : 0)<<' ';
		else g<<"Ciclu negativ!";
	g<<'\n';
	f.close(); g.close();
	return 0;
}