// https://goo.gl/fBmFxu
#include <bits/stdc++.h>

using namespace std;

#define NMAX        100009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>
#define x first
#define c second
#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here


// your solution is here
vector<edge>G[NMAX];
int n, m, start;
vector<int> d;

bool BellmanFord(int start, vector<int>&d) {
    for (int i = 1; i <= n; ++i) {
        d[i] = kInf;
    }

    queue<int>q;
    vector<int>qcnt(n + 1, 0);

    q.push(start);
    d[start] = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (auto &p : G[node]) {
            int x = p.x,  c = p.c;

            if (d[node] + c < d[x]) {
                d[x] = d[node] + c;
                q.push(x);
                ++qcnt[x];
                if (qcnt[x] == n) return false;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (d[i] == kInf) {
            d[i] = 0;
        }
    }
    return true;
}

void solve() {

    cin >> n >> m;

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

    d.resize(n + 1);

    bool e_ok = BellmanFord(1, d);
    if (e_ok) {
        for (int i = 2; i <= n; ++i) {
            cout << d[i] << " ";
        }
    } else {
        cout << "Ciclu negativ!\n";
    }
    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    d.clear();
}

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
   // auto cin_buff = cin.rdbuf();
   // auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    //ifstream fin("bellmanford.in");
   // cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
   // ofstream fout("bellmanford.out");
    //cout.rdbuf(fout.rdbuf()); // save and redirect


//     cin >> test_cnt;

    while (test_cnt--) {
        solve();
    }

    // restore pentru cin si cout
//    cin.rdbuf(cin_buff);
//    cout.rdbuf(cout_buff);

    return 0;
}