#include <bits/stdc++.h>

using namespace std;

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


int n,m,a,b,cost,d[50005];
vector <pair<int,int>> v[50005];

void Bellmanford(){
    for (int i = 1; i <= n - 1; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 0; k < v[j].size(); k++){
                if (d[j] + v[j][k].second < d[v[j][k].first])
                    d[v[j][k].first] = d[j] + v[j][k].second;
            }
        }
    }
}


int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b>>cost;
    v[a].push_back({b, cost});
}
for (int i = 1; i <= n; i++){
    d[i] = 999999999;
}
d[1] = 0;
Bellmanford();
int ok = 0;
for (int j = 1; j <= n && ok == 0; j++){
    for (int k = 0; k < v[j].size(); k++){
        if (d[j] + v[j][k].second < d[v[j][k].first]){
            ok = 1;
            break;
        }
    }
}
if (ok == 1)
    fout << "Ciclu negativ!";
else{
    for (int i = 2; i <= n; i++){
        fout << d[i] << " ";
    }
}

return 0;
}