#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <algorithm>
#define NMAX 50009  // ATENTIE la cat e in problema curenta !!!
#define MMAX 250009  // ATENTIE la cat e in problema curenta !!!
#define oo (1 << 30) // ATENTIE la cat e in problema curenta !!!
using namespace std;

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

// tipul edge
// muchia de cost "cost", de la node la neighbour,
// va fi un element edge(neighbour, cost) in G[node]
typedef pair<int, int> edge;
#define neighbour first
#define cost second

// aceleasi semnificatii ca la BFS
int n, m;
int d[NMAX], p[NMAX], used[NMAX];
vector<edge> G[NMAX];

//coada
queue<int> Q;

void read_input() {
    f >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y, c; // x -> y, de cost c
        f >>  x >> y >> c;

        G[x].push_back(edge(y, c));
        // G[y].push_back(edge(x, c)); // sterg daca e orientat !!!
    }
}


// return true = ciclu de cost negativ
// return false = nu are ciclu de cost negativ
bool BellmanFord(int source) {
    // ETAPA 1
    for (int i = 1; i <= n; ++i) {
        d[i] = oo;
        p[i] = oo;
    }

    // ETAPA 2
    Q.push(source);
    d[source] = 0;
    p[source] = 0;

    // ETAPA 3
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();

        ++used[node];
        if (used[node] == n) {
            return true; // am gasit ciclu de cost negativ
        }

        for (auto it = G[node].begin(); it != G[node].end(); ++it) {
            int neighbour = it->neighbour;
            int cost_edge = it->cost;

            if (d[ node ] + cost_edge < d[ neighbour ]) {
                d[ neighbour ] = d[ node ] + cost_edge;
                p[ neighbour ] = node ;

                Q.push( neighbour );
            }
        }
    }

    // ETAPA 4 - daca e cazul
    return false;
}

// in solve scriu tot ce tine de rezolvare - e ca un main
void solve() {
    // pe infoarena sursa este 1
    if (BellmanFord(1)) {
        g << "Ciclu negativ!\n";
    } else {
        for (int i = 2; i <= n; ++i) {
            g << d[i] <<  " ";
        }
        g << "\n";
    }
}

// rebuild source -> ... -> node (if exists)
void rebuild_path_recursive(int node, int source) {
    if (d[ node ] == oo) {
        g << "Drum inexistent!";
        return;
    }

    if (node == source) { // sau p[node] = 0; // conditie echivalenta
        g << node << " ";
        return;
    }

    // rebuild first source -> ...-> p[node]
    rebuild_path_recursive(p[node], source);

    // then p[node] -> node
    g << node << " ";
}

// puteti pastra main-ul mereu cum e acum
int main() {

    read_input();
    solve();
    // print_output();

    return 0;
}