#include <iostream>
#include <fstream>
#include <vector>

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

struct muchie{
    int vecin, cost;
};
vector<muchie>graf[50005];
int distTo[50005], N, M, x, y, c;

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= N; i++){
        fin >> x >> y >> c;
        muchie m; m.vecin = y; m.cost = c;
        graf[x].push_back(m);
    }

    for(int i = 1; i <= N; i++)
        distTo[i] = INT_MAX;

    distTo[1] = 0;
    for(int i = 1; i < M; i++)
        for(int i = 1; i <= N; i++)
            for(auto x: graf[i])
                if(distTo[i] + x.cost < distTo[x.vecin])
                    distTo[x.vecin] = distTo[i] + x.cost;

    for(int i = 1; i <= N; i++)
            for(auto x: graf[i])
                if(distTo[i] + x.cost < distTo[x.vecin]){
                    cout << "Ciclu negativ!";
                    return 0;
                }

    for(int i = 2; i <= N; i++)
        fout << distTo[i] << ' ';


    return 0;
}