#include <bits/stdc++.h>
#define readFast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define nl cout << '\n'
#define afis(v) for (auto x : v) {cout << x << " ";} cout << '\n';
#define afisPii(v) for (auto x : v) {cout << x.first << " " << x.second << '\n';} cout << '\n';
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 50005;

vector<pair<int,int>> graf[N];
int n, m;
bool in[N];
int lg[N];
bool cicluNegativ = false;

void dfs(int nod) {
    in[nod] = true;

    for (auto &[to, c] : graf[nod]) {
        if(in[to] == true) {
            //check ciclu
            if((lg[nod] + c) - lg[to] < 0)
                cicluNegativ = true;
            continue;
        }
        lg[to] = min(lg[to], lg[nod] + c);
        dfs(to);
    }
    in[nod] = false;
}

int main() {
    //ifstream fin("date.in.txt");
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graf[a].push_back({b, c});
    }
    fill(lg, lg + N, 1000000);
    lg[1] = 0;
    dfs(1);

    if(cicluNegativ)
        fout << "Ciclu negativ!";
    else {
        for (int i = 2; i <= n; ++i)
            fout << lg[i] << " ";
    }

    return 0;
}