# include <bits/stdc++.h>
# define MOD 200017
# define INF 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct node;
struct edgeNode;

struct edgeNode {
    int cost;
    node* nod;
};

struct node {
    int label, cnt, distance;
    vector <edgeNode> edges;
};

// X -> X % MOD
// X + MOD -> (X + MOD) % MOD = X % MOD

vector <node*> HASH[MOD];
int n, m, x, y, cost;

node* getNode (int label) {
    for (int i=0; i<HASH[label % MOD].size(); ++i)
        if (HASH[label % MOD][i]->label == label)
            return HASH[label % MOD][i];

    return NULL;
}

int main () {
    f>>n>>m;

    for (int i=1; i<=n; ++i) {
        node* nod = new node();
        nod->label = i;
        nod->edges.clear();
        if (i==1) nod->distance = 0;
             else nod->distance = INF;

        HASH[i % MOD].push_back(nod);
    }

    for (int i=1; i<=m; ++i) {
        f>>x>>y>>cost;

        edgeNode edge;
        edge.cost = cost;
        edge.nod = getNode(y);
        (getNode(x)->edges).push_back(edge);
    }

    queue<node*> q;
    q.push(getNode(1));
    (getNode(1)->cnt)++;

    while (!q.empty()) {
        node* nod = q.front();
        q.pop();

        for (auto &x: nod->edges) {
            if (nod->distance + x.cost < (x.nod)->distance) {
                x.nod->distance = nod->distance + x.cost;
                ++(x.nod->cnt);

                if (x.nod->cnt == n) {
                    g<<"Ciclu negativ!\n";
                    return 0;
                }
                q.push(x.nod);
            }
        }
    }

    for (int i=2; i<=n; ++i) {
        node* nod = getNode(i);
        g<<nod->distance<<" ";
    }


    return 0;
}