#include <fstream>
using namespace std;

#define dim 250001

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

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

long long 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;
	
	while (ok){
		ok=0;
		for (i=1; i<=m; i++)
			if (d[G[i].y]>d[G[i].x]+G[i].c){
				ok=1;
				d[G[i].y]=d[G[i].x]+G[i].c;
				if (++a[i]==n){
                    fo << "Ciclu negativ!\n";
                    return 0;
                }
			}
	}
	
	for (i=2; i<=n; i++) fo << d[i] << " ";
	
	return 0;
}