#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

const int NMAX = 50000 + 1, INF = 0x3f3f3f3f;

struct Muchie {
    int nod, cost;
    Muchie (int nod, int cost) {
        this->nod = nod;
        this->cost = cost;
    };
};

int n, m;
vector <Muchie> graf[NMAX];
int cost[NMAX], viz[NMAX];
bool inQ[NMAX];
queue <int> Q;

void citeste() {
    int a, b, c;
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        graf[a].push_back(Muchie(b, c));
    }
}

bool rezolva() {
    int nod, l, c, nod2;
    for (int i = 2; i <= n; i++) cost[i] = INF;
    Q.push(1);
    inQ[1] = true;
    viz[1]++;
    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;
        l = graf[nod].size();
        for (int i = 0; i < l; i++) {
            c = graf[nod][i].cost;
            nod2 = graf[nod][i].nod;
            if (cost[nod2] > c + cost[nod]) {
                cost[nod2] = c + cost[nod];
                if (!inQ[nod2]) {
                    if (viz[nod2] > n) return true;
                    viz[nod2]++;
                    inQ[nod2] = true;
                    Q.push(nod2);
                }
            }
        }
    }
    return false;
}

void scrie() {
    for (int i = 2; i <= n; i++) g << cost[i] << ' ';
    g << '\n';
}

int main() {
    bool sol;
    citeste();
    sol = rezolva();
    if (sol) g << "-Ciclu negativ!\n";
    else scrie();
    return 0;
}