#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define INF 1e9
#define NMAX 50005
vector<pair<int,int>> v[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int> > > h;
int n, m, a, b, c, nod, d[NMAX], g[NMAX];
int main() {
    fin >> n >> m;
    for (int i=1;i<=m;i++){
        fin >> a >> b >> c;
        v[a].push_back({c, b});
    }
    for (int i=1;i<=n;i++)
        d[i] = INF;
    d[1] = 0;
    h.push({0, 1});
    while(!h.empty()){
        nod = h.top().second;
        h.pop();
        for (int i=0;i<v[nod].size();i++){
            if (d[nod] + v[nod][i].first < d[v[nod][i].second]){
                g[v[nod][i].second] ++;
                d[v[nod][i].second] = d[nod] + v[nod][i].first;
                h.push({d[v[nod][i].second], v[nod][i].second});
                if (g[v[nod][i].second] == n){
                   fout << "Ciclu negativ!\n";
                   return 0;
                }
            }
        }
    }
    for (int i=2;i<=n;i++){
        fout << d[i] << ' ';
    }
    return 0;
}