#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+5;
const int oo = 0x3f3f3f3f;

int n;
vector<int> cost, cnt;
vector<vector<pii>> e;

void read(), bellmanford();

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

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