#include<stdio.h>
#include<set>
#include<vector>

using namespace std;
#define NMAX 50001
#define INF 50000000

void citire();
void tipar();
bool bellmanford(int sursa);


int N , M  , d[NMAX];
vector<int> G[NMAX] , C[NMAX] ; 
struct Compare{
	bool operator()(int a , int b){
		return d[a] < d[b];
	}
};
multiset<int,Compare> Q;
int viz[NMAX];

int main()
{
	citire();
	tipar();
	return 0;
}

void citire()
{
	int x , y , c;
	freopen("bellmanford.in" , "r" , stdin );
	scanf("%d%d" , &N  ,&M );
	for(int i = 1 ; i <= M ; ++i ) {
		scanf("%d%d%d" , &x , &y , &c );
		G[x].push_back(y);
		C[x].push_back(c);
	}
}

bool bellmanford(int sursa)
{
	int nod;
	for(int i = 1 ; i <= N ; ++i )
		d[i] = INF;
	d[sursa] = 0;
	Q.insert(sursa);
	while(!Q.empty()) {
		nod = *Q.begin();
		Q.erase(Q.begin());
		for(int i = 0 ; i < G[nod].size() ; ++i )
			if(d[nod] + C[nod][i] < d[G[nod][i]]) {
				d[G[nod][i]] = d[nod] + C[nod][i];
				if(++viz[G[nod][i]] == N)
					return 0;
				Q.insert(G[nod][i]);
			}
	}
	return 1;
}

void tipar()
{
	freopen("bellmanford.out" , "w" , stdout );
	if(bellmanford(1))
		for(int i = 2 ; i <= N ; ++i )
			printf("%d " , d[i] );
	else
		printf("Ciclu negativ!");
}