#include <bits/stdc++.h>

#define NMAX 50002

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

int frq[NMAX], n, m, x, y, c, cost[NMAX];
vector< pair<int, int> > vecini[NMAX];
queue<int> q;

void initCost(){
    for(int i = 1; i <= n; i ++)
        cost[i] = 99999999;
}

void blmford(int x){
    q.push(x);
    cost[x] = 0;
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        if(frq[nod] >= n){
            g << "Ciclu negativ!";
            return;
        }
        for(auto vecin : vecini[nod]){
            if(cost[vecin.first] > cost[nod] + vecin.second){
               cost[vecin.first] = cost[nod] + vecin.second;
               q.push(vecin.first);
               frq[vecin.first] ++;
            }
        }
    }
    for(int i = 2; i <= n; i ++) g << cost[i] << " ";
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i ++){
        f >> x >> y >> c;
        vecini[x].push_back(make_pair(y, c));
    }
    initCost();
    blmford(1);

    return 0;
}