#include <bits/stdc++.h>
#define MAX 100005
using namespace std;

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


struct cmp{
    bool operator()(int a, int b){
        return a > b;
    }
};

priority_queue < int, vector < int > , cmp > q;
vector < pair < int , int > > g[MAX];

int n, m, x, y, fv[MAX], d[MAX], cost;
bool c[MAX];
const int oo = (1 << 30);

bool BF(int k){
    c[k] = true;
    q.push(k);
    for(int i = 1; i <= n; i++)
        d[i] = oo;
    d[k] = 0;

    while(!q.empty()){
        k = q.top();
        q.pop();
        fv[k]++;
        if(fv[k] >= n)
            return false;

        for(int i = 0; i < g[k].size(); i++){
            int vec = g[k][i].first;
            cost = g[k][i].second;

            c[k] = false;
            if(d[vec] > d[k] + cost){
                d[vec] = d[k] + cost;
                if(!c[vec])
                    c[vec] = true, q.push(vec);
            }
        }
    }

    return true;
}

int main(){
    in>>n>>m;
    while(m){
        in>>x>>y>>cost;
        g[x].push_back({ y, cost });
        m--;
    }

    if(BF(1))
        for(int i = 2; i <= n; i++)
            out<<d[i]<<" ";
    else
        out<<"Ciclu negativ!";
}