#include <bits/stdc++.h>
#define MAX 50005
#define oo (1 << 30)
using namespace std;

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

vector < pair < int , int > > g[MAX];
queue < int > q;
bitset < MAX > c;
int fv[MAX], d[MAX];

int n, m, x, y, cost;

bool Bellman_Ford(int k){
    for(int i = 1; i <= n; i++)
        d[i] = oo;
    d[k] = 0;
    q.push(k);
    c[k] = true;
    while(!q.empty()){
        fv[k]++;
        k = q.front();
        if(fv[k] >= n)
            return false;
        q.pop();
        c[k] = false;

        for(int i = 0; i < g[k].size(); i++){
            int vec = g[k][i].first;
            cost = g[k][i].second;
            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});
    }

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

}