#include <fstream>
#include <vector>
using namespace std;

#define dim 250001

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

vector< pair <int,int> > G[dim];
vector< int > Q;

int d[dim],in[dim],a[dim],i,n,m,x,y,c;

int main(){
	
	fi >> n >> m;
	for (i=1; i<=m; i++){
		fi >> x >> y >> c;
		G[x].push_back(make_pair(y,c));
	}
	for (i=2; i<=n; i++) d[i]=0x3f3f3f3f;
	
	Q.push_back(1);
	
	while (!Q.empty()){
		int nod=Q.back();
		Q.pop_back();
		in[nod]=0;
		for (vector< pair < int,int> >::iterator it=G[nod].begin(); it!=G[nod].end(); it++){
			if (d[it->first]>d[nod]+it->second){
				d[it->first]=d[nod]+it->second;
				if (!in[it->first]) {
					Q.push_back(it->first);
				}
				if (++a[it->first]==n){
					fo << "Ciclu negativ!";
					return 0;
				}
			}
		}
	}
	
	for (i=2; i<=n; i++) fo << d[i] << " ";
	
	return 0; 
}