#include <iostream>
#include <fstream>
#include <utility>
#include <queue>
#include <vector>
#include <bitset>
#include <cstring>
#define NMAX 50005
#define oo 0x3f3f3f3f
using namespace std;

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

int n, m, dist[NMAX], inqs[NMAX];
vector < pair < int, int > > nodes[NMAX];
bitset <NMAX> inq;

void bellFord () {
	memset(dist, oo, sizeof(dist));
	queue <int> q;
	q.push(1);
	inq[1] = 1;
	dist[1] = 0;
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		inq[node] = 0;
		for (int i = 0; i < nodes[node].size(); ++i) {
			if (dist[nodes[node][i].first] > dist[node] + nodes[node][i].second) {
				dist[nodes[node][i].first] = dist[node] + nodes[node][i].second;
				if (inq[node]) {
					continue;
				}
				if (++ inqs[nodes[node][i].first] > n) {
					fout << "Ciclu negativ!\n";
					return;
				}
				inq[nodes[node][i].first] = 1;
				q.push(nodes[node][i].first);
			}
		}
	}
	for (int i = 2; i <= n; ++i) {
		fout << dist[i] << " ";
	}
}

int main ()
{
	fin >> n >> m;
	int x, y, c;
	for (int i = 1; i <= m; ++i) {
		fin >> x >> y >> c;
		nodes[x].push_back(make_pair(y, c));
	}
	bellFord();
	
	return 0;
}