#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 = 50055;
const int M = 250055;

struct muchie{
    int a, b, c;
} e[M];
vector<pair<int,int>> graf[N];
int n, m, drum[N], fr[N];
bool in[N], cicluNegativ = false;
queue<int> coada;

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) {
        fin >> e[i].a >> e[i].b >> e[i].c;
        graf[e[i].a].push_back({e[i].b, e[i].c});
    }
    fill(drum, drum + N, INT_MAX);

    drum[1] = 0;
    fr[1] = 1;
    coada.push(1);

    while(!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        in[nod] = false;

        for (auto x : graf[nod]) {
            int to = x.first, c = x.second;

            if(drum[to] > drum[nod] + c) {
                drum[to] = drum[nod] + c;

                if(in[to] == false) {
                    in[to] = true;
                    coada.push(to);
                    ++fr[to];

                    if(fr[to] >= n) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        fout << drum[i] << " ";

    return 0;
}