#include <fstream>
#include <vector>
#include <queue>

using namespace std;
#define Nmax 50005
#define Inf (1<<30)
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int, int>>g[Nmax];
int n, m, cost[Nmax];

int bell() {
	int i, k;
	for (i = 1; i <= n; i++) {
		cost[i] = Inf;
	}
	cost[1] = 0;
	for (k = 1; k <= n; k++) {
		for (i = 1; i <= n; i++) {
			for (auto nc : g[i]) {
				if (cost[i] + nc.second >= cost[nc.first]) continue;
				cost[nc.first] = cost[i] + nc.second;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		for (auto nc : g[i]) {
			if (cost[i] + nc.second < cost[nc.first]) return -1;
		}
	}
	return 0;
}

int main() {
	int i, x, y, z;
	fin >> n >> m;
	for (i = 0; i < m; i++) {
		fin >> x >> y >> z;
		g[x].push_back({ y, z });
	}
	if (bell() == -1) fout << "Ciclu infinit!";
	for (i = 2; i <= n; i++) {
		if (cost[i] == Inf) fout << 0 << ' ';
		else fout << cost[i] << ' ';
	}
}