#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first
#define se second
#define pb push_back

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int N = 5e4+3;
const int oo = 0x3f3f3f3f;

int n;
vector<vector<pii>> e;
vector<int> cnt, cst;
void read(), bellmanford();

int main()
{
	read(); 
	bellmanford();
	for (int i = 2; i <= n; i++) g << cst[i] << ' ';

	return 0;
}

void read(){
	int m;
	f >> n >> m; 
	e.resize(n+3); cnt.resize(n+3); cst.resize(n+3, oo);
	while (m--){
		int a, b, c; f >> a >> b >> c;
		e[a].pb({b,c});
	}
}
void bellmanford(){
	queue<pii> q; q.push({1, 0}); cst[1] = 0;
	while (!q.empty()){
		int from, c; tie(from, c) = q.front(); q.pop();
		for (auto it: e[from]){
			int to, cm; tie(to, cm) = it;
			if (cm + c < cst[to]){
				cnt[to]++; 
				if (cnt[to] == n+3) {g << "Ciclu negativ!"; exit(0);}
				cst[to] = cm + c;
				q.push({to, cst[to]});
			}
		}
	}
}