#include <bits/stdc++.h>
#define Nmax 50005
#define INF 2e9
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int N, M;
vector<pair<int, int> > G[Nmax];
queue<int> Q;
int dist[Nmax], nr[Nmax];
int main()
{
f >> N >> M;
for (int i = 1; i <= M; ++i) {
int x, y, d;
f >> x >> y >> d;
G[x].push_back({y, d});
}
for (int i = 2; i <= N; ++i)
dist[i] = INF;
Q.push(1);
while (!Q.empty()) {
int node = Q.front();
Q.pop();
for (auto it: G[node])
if (dist[it.first] > dist[node] + it.second) {
int node2 = it.first, D = it.second;
++nr[node2];
if (nr[node2] == N) {
g << "Ciclu negativ!\n";
return 0;
}
dist[node2] = dist[node] + D;
Q.push(node2);
}
}
for (int i = 2; i <= N; ++i)
g << dist[i] << " ";
return 0;
}