#include <fstream>
using namespace std;

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

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

long d[300000],a[300000],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;
}