#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
#define nm 50050
#define mp make_pair
#define INF 1000000000
vector <pair<int,int> > a[nm];
FILE *f,*g;
bitset <nm> again;
int ag[nm],cost[nm];
class comp {
public :
bool operator () (const int & i, const int & j) const 
{
return (cost[i]>cost[j]);
}
};
priority_queue <int, vector <int>,comp>H;
bool ciclu;
int n,m,i;


void read() {
int x,y,c,i;
f=fopen("bellmanford.in","r");
g=fopen("bellmanford.out","w");
fscanf(f,"%d%d",&n,&m);

for (i=1;i<=m;i++) {
	fscanf(f,"%d%d%d",&x,&y,&c);
	a[x].push_back(mp(y,c));
	}
}

void init() {
int i;

cost[1]=0;
for (i=2;i<=n;i++) cost[i]=INF;
}

void bellman() {
int j,x;
	
H.push(1);
ag[1]++;
again[1]=true;

while (!H.empty()) {
	x=H.top();
	H.pop();
	for (j=0;j<a[x].size();j++) 
		if (cost[a[x][j].first]>cost[x]+a[x][j].second) {
			cost[a[x][j].first]=cost[x]+a[x][j].second;
			if (!again[a[x][j].first]) {
				if (ag[a[x][j].first]>=n) 
					ciclu=true;
				else {
					ag[a[x][j].first]++;
					again[a[x][j].first]=true;
					H.push(a[x][j].first);
					}
				
				}
				
			}
	}

}


int main() {
read();
init();
bellman();

if (ciclu) 
	fprintf(g,"Ciclu negativ!");
else 
	for (i=2;i<=n;i++) fprintf(g,"%d ",cost[i]);

	
fclose(g);
return 0;
}