#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct muchie{
int x, c;
};
const int N = 50002;
vector<muchie> g[N];
int dist[N], viz[N], nrViz[N], n, m;
queue<int> Q;
int main(){
int i, x, y, c;
fin >> n >> m;
for(i=1;i<=m;i++){
fin >> x >> y >> c;
g[x].push_back({y, c});
//g[y].push_back({x, c});
}
for(i=2;i<=n;i++)
dist[i] = INT_MAX;
Q.push(1);
viz[1] = 1;
nrViz[1] = 1;
while(!Q.empty()){
int nod = Q.front();
viz[nod] = 0;
Q.pop();
for(muchie e : g[nod]){
int vecin = e.x;
int cost = e.c;
if(dist[vecin] > dist[nod] + cost){
dist[vecin] = dist[nod] + cost;
if(viz[vecin] == 0){
Q.push(vecin);
viz[vecin] = 1;
//
}
nrViz[vecin]++;
if(nrViz[vecin] >= n){
/// ciclu negativ
fout << "Ciclu negativ!";
return 0;
}
}
}
}
for(i=2;i<=n;i++)
fout << dist[i] << " ";
}