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

using namespace std;

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

const int NMAX = 50000 + 1;
const int INF = 0x3fffffff;
int n, m;
int cost[NMAX], vizitat[NMAX];
bool inQ[NMAX];
queue <int> Q;
vector < pair <int, int> > graf[NMAX];

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

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

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

int main() {
    citeste();
    bool ok = BellmanFord();
    if (!ok) scrie();
    else g << "Ciclu negativ!";
    g << '\n';
    return 0;
}