#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <queue>
#include <vector>

#define In "bellmanford.in"
#define Out "bellmanford.out"
#define Nmax 50001

using namespace std;

FILE *fin = fopen(In, "r");
FILE *fout = fopen(Out, "w");

vector <int> V[Nmax], C[Nmax];
queue <int> q;

int N, M;

#define BUF 1 << 17
char buf[BUF];
int pos = BUF;

inline char next()  {
	if(pos == BUF)
		fread(buf, 1, BUF, fin), pos = 0;
	return buf[pos++];
}

inline int read()  {
	int x = 0, semn = 1;
	
	char ch = next();
	while(!isdigit(ch) && ch != '-')  {
		ch = next();
	}
	
	if(ch == '-')
		semn = -1, ch = next();
		
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = next();
	
	return x * semn;
}

int d[Nmax], w[Nmax];
#define inf 1 << 30


int main(void)  {
	N = read(), M = read();
	for(int i = 0;i < M;i++)  {
		int x = read(), y = read(), c = read();
		V[x].push_back(y);
		C[x].push_back(c);
	}
	
	for(int i = 2;i <= N;i++)
		d[i] = inf;
	q.push(1);
	
	while(!q.empty())  {
		int el = q.front();
		w[el]++;
		if(w[el] > N)  {
			fprintf(fout, "Ciclu negativ!\n");
			return 0;
		}
		for(int j = 0;j < V[el].size();j++)  {
			if(d[el] + C[el][j] < d[V[el][j]])  {
				d[V[el][j]] = d[el] + C[el][j];
				q.push(V[el][j]);
			}
		}
		q.pop();
	}
	
	for(int i = 2;i <= N;i++)
		fprintf(fout, "%d ", d[i]);
	
	fclose(fin);
	fclose(fout);
	return 0;
}