#include<fstream>
#include<queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,cost[50005],pas,a,b,c,w;
struct nod
{ int nr;
  int c;
  nod *urm;
} *v[50005],*p;
queue<int> q;

int apartine(int x)
{ queue<int> q2=q;
  while(!q2.empty())
	  { if(q2.front()==x) return 1;
	    q2.pop();
	  }
  return 0;
}

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;
	while(!q.empty()&&pas<n)
		{ ++pas;
		  w=q.front();
		  q.pop();
		  p=v[w];
		  while(p)
			  { if(cost[p->nr]>cost[w]+p->c)
				  { cost[p->nr]=cost[w]+p->c;
				    if(!apartine(p->nr)) q.push(p->nr);
				  }
				p=p->urm;
			  }
		}
	if(q.empty()) for(i=2;i<=n;i++) g<<cost[i]<<' ';
		else g<<"Ciclu negativ!";
	g<<'\n';
	f.close(); g.close();
	return 0;
}