#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const long long INF = 1e18;

int main(){
    ifstream reader("bellmanford.in");
    ofstream writer("bellmanford.out");

    int n, m;
    reader >> n >> m;

    vector< vector< pair<int,int> > > graf(n+1);

    for(int i=0; i<m; i++){
        int x, y, c;
        reader >> x >> y >> c;
        graf[x].push_back( make_pair(y, c) );
    }

    vector<long long> dist(n+1, INF);
    vector<int> inQ(n+1, 0);
    vector<int> cnt(n+1, 0);

    queue<int> coada;

    int s = 1;
    dist[s] = 0;
    inQ[s] = 1;
    cnt[s] = 1;
    coada.push(s);

    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        inQ[nod] = 0;

        for(int i=0; i<graf[nod].size(); i++){
            int vecin = graf[nod][i].first;
            int cost  = graf[nod][i].second;

            if(dist[nod] < INF && dist[nod] + cost < dist[vecin]){
                dist[vecin] = dist[nod] + cost;

                if(inQ[vecin] == 0){
                    coada.push(vecin);
                    inQ[vecin] = 1;
                    cnt[vecin]++;

                    if(cnt[vecin] > n){
                        writer << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i=2; i<=n; i++){
        if(dist[i] == INF) 
            writer << 0 << " ";
        else 
            writer << dist[i] << " ";
    }

    return 0;
}