#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

typedef pair<int, int> Edge;

int n, m, d[50001];
bool better[50001];
vector<Edge> g[50001];
const int INF = 1e7;
void citire();


int main() {
    citire();
    ofstream out("bellmanford.out");

    bool changed = true;
    int k;

    for (k = 1; k < n; ++k) {
        changed = false;
        for (int x = 1; x <= n; ++x) {
            if (d[x] == INF) continue;
            if (!better[x]) continue;
            for (int i = 0; i < g[x].size(); ++i) {
                int y = g[x][i].second;
                if (d[x] + g[x][i].first < d[y]) {
                    d[y] = d[x] + g[x][i].first;
                    better[y] = true;
                    changed = true;
                }
            }
            better[x] = false;
        }

        if (!changed) break;
    }

    if (k == n) {
        for (int x = 1; x <= n; ++x) {
            if (d[x] == INF) continue;
            for (int i = 0; i < g[x].size(); ++i) {
                int y = g[x][i].second;
                if (d[x] + g[x][i].first < d[y]) {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }




    for (int i = 2; i <= n; ++i) {
        out << d[i] << " ";
    }

    return 0;
}


void citire() {
    ifstream in("bellmanford.in");

    in >> n >> m;
    for (int i = 1, x, y, c; i <= m; ++i) {
        in >> x >> y >> c;
        g[x].push_back(make_pair(c, y));
    }

    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }

    d[1] = 0;
    better[1] = true;

    in.close();
}