#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;
bool cNeg = false;

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

void blmford(int x){
    q.push(x);
    while(!q.empty() && !cNeg){
        int nod = q.front();
        q.pop();
        if(frq[nod] > n) cNeg = true;
        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] ++;
            }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i ++){
        f >> x >> y >> c;
        vecini[x].push_back(make_pair(y, c));
        vecini[y].push_back(make_pair(x, c));
    }
    initCost();
    blmford(1);
    if(cNeg) g << "Ciclu negativ!";
    else for(int i = 1; i <= n; i ++) g << cost[i] << " ";
    return 0;
}