#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
#define DIM 50002
#define inf 30000

using std::ifstream;
using std::ofstream;
using std::vector;

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

class Node_adj {
public:
    int y, cost;
    Node_adj(int y, int cost): y{y},cost{cost}{}
};

class NODE {
public:
    int dist, d, f, p;
    bool marked;
};


void read(int &n, int& m, vector<Node_adj> G[]) {

    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, cost;
        f >> x >> y >> cost;
        G[x].push_back(Node_adj(y,cost));
    }
    f.close();
}

void initialize(int n, NODE node[], int s) {
    for (int i = 1; i <= n; i++) {
        node[i].dist = inf;
        node[i].p = -1;
    }
    node[s].dist = 0;
}

void relax(int x, int y, vector<Node_adj> G[], NODE node[]) {
    int cost;
    for (auto n : G[x]) {
        if (n.y == y) {
            cost = n.cost;
            break;
        }
    }
    if (node[y].dist > node[x].dist + cost) {
        node[y].dist = node[x].dist + cost;
        node[y].p = x;
    }
}

bool BellmanFord(int n, vector<Node_adj> G[], NODE node[], int s) {
    initialize(n, node, s);
    for (int i = 1; i <= n-1; i++) {
        for (int q = 1; q <= n; q++) {
            for (auto j : G[q]) {
                relax(i, j.y, G, node);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto j : G[i]) {
            if (node[j.y].dist > node[i].dist + j.cost) {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    NODE node[DIM];
    vector<Node_adj> G[DIM];
    int n, m;
    read(n, m, G);
    ofstream f("bellmanford.out");
    if (BellmanFord(n, G, node, 1)) {
        for (int i = 2; i <= n; i++) {
            g << node[i].dist << " ";
        }
    }
    else {
        g << "Ciclu negativ!";
    }
    g.close();
    return 0;
}