#include <fstream>
#include <vector>
#include <climits>
#define INF INT_MAX
using namespace std;

struct arc {int y, c;};

int viz[50005];

int main() {
    int d[50005], n, m, i, j, ok, x;
    vector<arc> v[50005];
    arc z;

    ifstream in ("bellmanford.in");
    in >> n >> m;
    z.y = z.c = 0;
    v[0].push_back(z);
    for (i = 1; i <= m; i++) {
        in >> x >> z.y >> z.c;
        v[x].push_back(z);
    }
    in.close ();

    for (i = 1; i <= n; i++)
        d[i] = INF;
    d[1] = 0;

    for (i = 1; i <= n; i++) {
        ok = 0;
        for (j = 1; j <= n; j++)
            if (d[j] != INF && !viz[j]) {
                for (vector<arc>::iterator it = v[j].begin(); it != v[j].end(); it++) {
                    arc jt = *it;
                    if (d[jt.y] > d[j] + jt.c) {
                        d[jt.y] = d[j] + jt.c;
                        ok = 1;
                    }
                }
                if (!ok)
                    viz[j] = 1;
            }
    }

    ofstream out("bellmanford.out");
    if (ok)
        out << "Ciclu negativ!";
    else for (i = 2; i <= n; i++)
            out << d[i] << ' ';
    out.close();

    return 0;
}