#include <fstream>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

#include <climits>

using namespace std;



ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");



const int MAXN = 50005;

int n, m;

vector<pair<int, int>> v[MAXN];

queue<int> q;

bool viz[MAXN];

int d[MAXN];





int main() {



    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {

        int a, b, c;

        fin >> a >> b >> c;

        v[a].push_back(make_pair(b, c));

        d[i] = INT_MAX;

    }



    d[1] = 0;

    q.push(1);

    viz[1] = 1;

    while(!q.empty()) {

        int node = q.front();

        for (int i = 0; i < v[node].size(); ++i) {

            int k = v[node][i].first;

            if (viz[k] == 1 && d[i] + v[node][i].second - d[k] < 0) {

                fout << "Ciclu negativ!";

                return 0;

            }

            if (d[k] > d[node] + v[node][i].second) {

                d[k] = d[node] + v[node][i].second;

                viz[k] = 1;

                q.push(k);

            }

        }

        q.pop();

    }



    for (int i = 2; i <= n; ++i) {

        fout << d[i] << ' ';

    }



    fout.close();

    return 0;

}