#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000000000000

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie
{
	int vf;
	long long int cost;
};

void citire();
bool bf();

bool ok=1;
int n, m, start = 1;
long long d[50005];
int gr[50005], prec[50005], nr[50005];
vector<muchie> G[50005];
queue<int> q;

int main(){
	citire();
	if (bf()){
		for (int i = 2; i <= n; i++)
			fout << d[i] << ' ';
	}
	else
        fout << "Ciclu negativ!"<<'\n';;
	return 0;
}

bool bf(){
	int x,i;
	muchie y;
	bool ok = true;
	q.push(start);

	while (!q.empty() && ok){
		x = q.front();
		q.pop();
		for (i = 0; i < gr[x]; i++){
			y = G[x][i];
			if (d[y.vf] > d[x] + y.cost){
				d[y.vf] = d[x] + y.cost;
				nr[y.vf]++;
				if (nr[y.vf] == n){
					ok = 0;
					break;
				}
				q.push(y.vf);
			}
		}
	}

	return ok;
}

void citire(){
	int x, i;
	muchie e;
	fin >> n >> m;
	for (i = 1; i <= m; i++){
		fin >> x >> e.vf >> e.cost;
		gr[x]++;
		G[x].push_back(e);
	}
	for (i = 1; i <= n; i++){
		nr[i] = 0;
		d[i] = INF;
	}
	d[1]=0;
}