#include <fstream>
#include <vector>

using namespace std;

struct edge{

    edge(int src, int dst, int cost) : src(src), dst(dst), cost(cost) {
    }

    int src, dst, cost;
};

const int NMAX = 50001;
const int MMAX = 250000;
const int INF = (1 << 30);
const int S = 1;

vector<edge> edges;
int cost[NMAX];

int main() {

    ifstream f("bellmanford.in");

    int n, m;
    f >> n >> m;

    for (int i = 0; i < m; ++i) {
        int src, dst, cost;
        f >> src >> dst >> cost;
        edges.push_back(edge(src, dst, cost));
    }

    for (int i = 1; i <= n; ++i) {
        if (i == S) {
            cost[i] = 0;
        }
        else {
            cost[i] = INF;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (cost[edges[j].src] + edges[j].cost < cost[edges[j].dst]) {
                cost[edges[j].dst] = cost[edges[j].src] + edges[j].cost; 
            }
        }
    }

    ofstream g("bellmanford.out");
    for (int i = 0; i < m; ++i) {
        if (cost[edges[i].src] + edges[i].cost < cost[edges[i].dst]) {
            g << "Ciclu negativ!\n";
            return 0;
        }
    }

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

    return 0;
}