#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int n, m, d[50005], update[50005];

vector <pair<int, int>> g[50005];

queue <int> q;

void BF(int nod){
    q.push(nod);
    d[nod] = 0;
    int k;
    while(!q.empty()){
        k = q.front();
        for(auto it:g[k]){
            if(it.second + d[k] < d[it.first]){
                d[it.first] = d[k] + it.second;
                q.push(it.first);
                update[it.first]++;
                if(update[it.first] == n){
                    out<<"CICLU NEGATIV";
                    exit(0);
                }
            }
        }
        q.pop();
    }
}

int main(){
    in>>n>>m;
    int x, y, c;
    while(in>>x>>y>>c){
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }
    for(int i = 1; i <= n; i++){
        d[i] = 1<<29;
    }
    BF(1);
    for(int i = 1; i <= n; i++){
        if(d[i] == 1<<29) out<<"-1 ";
        else out<<d[i]<<" ";
    }
    return 0;
}