#include<fstream>
#include<queue>
#include<vector>
#define inf 1000000000
using namespace std;
vector <pair<int,int> > a[50001];
queue <int> q;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int i,j,k,n,m,x,y,c,viz[50001],d[50001];;

int main(){
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>x>>y>>c;
		a[x].push_back(make_pair(y,c));
	}
	for(i=1;i<=n;i++)
		d[i]=inf;
	q.push(1);
	viz[1]=1;
	d[1]=0;
	while(!(q.empty())){
		k=q.front();
		for(i=0;i<a[k].size();i++){
			int nod=a[k][i].first;
			int cost=a[k][i].second;
			y=d[k]+cost;
			if(viz[nod]==0||y<d[nod]){
				q.push(nod);
				d[nod]=y;
				viz[nod]++;
				if(viz[nod]>n){
					g<<"Ciclu negativ!";
				return 0;}
			}
		}
	q.pop();
	}
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	return 0;
}