# include <fstream>
# include <queue>
# include <vector>
# define MAXN 50010
# define MAXM 250010
# define pb   push_back
# define INF  0x3f3f3f3f

using namespace std;

queue<int> q;
vector<int> L[MAXN], C[MAXN];
int n, m;
int cost[MAXN];
bool negative;

int main() {
    ifstream fin("bellmanford.in");
    fin >> n >> m;
    int x, y, c;
    for (int i=1; i<=n; ++i) {
        fin >> x >> y >> c;
        L[x].pb(y);
        C[x].pb(c);
    }
    fin.close();

    for (int i=2; i<=n; ++i)
        cost[i] = INF;

    q.push(1);
    while (!q.empty()) {
        if ((signed)q.size() > m)
            negative = 1;
        x = q.front();
        for (unsigned int i=0; i<L[x].size(); ++i) {
            if (cost[ L[x][i] ] > cost[x] + C[x][i]) {
                cost[ L[x][i] ] = cost[x] + C[x][i];
                q.push(L[x][i]);
            }
        }
        q.pop();
    }

    ofstream fout("bellmanford.out");
    if (negative)
        fout << "Ciclu negativ!";
    else for (int i=2; i<=n; ++i)
        fout << cost[i] << " ";
    fout.close();
    return 0;
}