#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <utility>
#include <climits>
#include <queue>
using namespace std;
ifstream be("bellmanford.in");
ofstream ki("bellmanford.out");
void beolvas(vector<vector<pair<int, int>>>& graf, int m);
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start);
bool bellman_ford_2(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p);
bool bellman_ford(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int> &d, vector<int> &p);
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p);
void bellman_ut(int v, vector<int>& d, vector<int>& p);
int main(){
int n, m, start;
be >> n >> m;
start = 0;
//be >> n >> m >> start;
//start--;
vector<vector<pair<int, int>>> graf(n);
beolvas(graf, m);
legrovidebb_ut(graf, n, start);
}
void beolvas(vector<vector<pair<int, int>>>& graf, int m) {
for (int i = 0; i < m; i++) {
int x, y, z;
be >> x >> y >> z;
graf[x - 1].push_back(make_pair((y - 1), z));
}
}
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start) {
vector<int> d(n, INT_MAX);
vector<int> p(n, -1);
if (bellman_ford_2(graf, n, start, d, p)) {
//ki << "Van negativ kor";
ki << "Ciclu negativ!";
}
else {
for (int i = 0; i < n; i++) {
if (i != start) {
if (d[i] != INT_MAX) {
ki << d[i] << " ";
//ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: " << d[i] << "\n";
//ki << "A legrovidebb ut " << i+1 << "-ba/be: ";
//bellman_ut(i, d, p);
}
else{
//ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: Nem lehet eljutni!\n";
//ki << "A legrovidebb ut " << i+1 << "-ba/be: Nem lehet eljutni!\n";
}
}
}
}
}
bool bellman_ford_2(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p) {
d[start] = 0;
queue<int>q;
q.push(start);
bool negativcycles = false;
vector<bool>in_queue(n + 1, false);
vector<int>cnt(n + 1, 0);
while (!q.empty() && !negativcycles) {
int x = q.front();
q.pop();
in_queue[x] = false;
for (auto p : graf[x])
{
if (d[x] < INT_MAX)
{
int v = p.second;
int edge = p.first;
if (d[edge] > d[x] + v)
{
d[edge] = d[x] + v;
if (!in_queue[edge])
{
if (cnt[edge] >= n)
negativcycles = true;
else
{
q.push(edge);
in_queue[edge] = true;
cnt[edge]++;
}
}
}
}
}
}
if (negativcycles) {
return true;
}
return false;
}
bool bellman_ford(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p) {
d[start] = 0;
for (int i = 0; i < n-1; i++)
for (int u = 0; u < n; u++)
relax(graf, u, d, p);
for (int u = 0; u < n; u++)
for (auto i : graf[u]) {
int w = i.first;
if ((d[u] != INT_MAX) && (d[w] > (d[u] + i.second)))
return true;
}
return false;
}
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p) {
for (auto i : graf[v]) {
int w = i.first;
if ((d[v] != INT_MAX) && (d[w] > (d[v] + i.second))) {
d[w] = d[v] + i.second;
p[w] = v;
}
}
}
void bellman_ut(int v, vector<int>& d, vector<int>& p) {
vector<int> ut;
ut.push_back(v);
while (p[ut[ut.size() - 1]] != -1) {
ut.push_back(p[ut[ut.size() - 1]]);
}
for (int i = ut.size() - 1; i >= 0; i--) {
ki << ut[i] + 1 << " ";
}
ki << "\n";
}