#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;
struct v{
    int a, b, c;
};

v edge[N];
int n, m, drum[N];
bool in[N], cicluNegativ = 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) {
        fin >> edge[i].a >> edge[i].b >> edge[i].c;
    }
    fill(drum, drum + N, 1000000);

    drum[1] = 0;
    for (int k = 2; k <= n; ++k) {
        for (int i = 1; i <= m; ++i) {
            int from = edge[i].a, to = edge[i].b, cost = edge[i].c;
            if(drum[from] + cost < drum[to]) {
                drum[to] = drum[from] + cost;
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
       int from = edge[i].a, to = edge[i].b, cost = edge[i].c;
       if(drum[from] + cost < drum[to]) {
            fout << "Ciclu negativ!";
            return 0;
       }
    }

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

    return 0;
}