#include <fstream>
using namespace std;

#define dim 250001

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

struct cell{int x,y,c;}G[dim];

int d[dim],a[dim],i,n,m;

int main(){
	
	fi >> n >> m;
	for (i=1; i<=m; i++) fi >> G[i].x >> G[i].y >> G[i].c;
	for (i=2; i<=n; i++) d[i]=0x3f3f3f3f;
	int ok=1; int aux;
	
	while (ok){
		ok=0;
		for (i=1; i<=m; i++){
			aux=d[G[i].x]+G[i].c;
			if (d[G[i].y]>aux){
				ok=1;
				d[G[i].y]=aux;
				if (++a[i]>n){
					fo << "Ciclu negativ!\n";
					return 0;
				}
			}
		}
	}
	
	for (i=2; i<=n; i++) fo << d[i] << " ";
	
	return 0;
}