#include <fstream>
#include <climits>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

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

#define NMAX 50005

int n, m, cost[NMAX], ct_coada[NMAX];
vector<pair<int, int>> G[NMAX];
bitset<NMAX> in_coada;
queue<int> q;

void citire() {
    f >> n >> m;
    int nod1, nod2, cost;
    for (int i = 0; i < m; i++) {
        f >> nod1 >> nod2 >> cost;
        G[nod1].push_back({nod2, cost});
    }
}

void initializare() {
    for (int i = 2; i <= n; i++)
        cost[i] = INT_MAX;
}

void element_nou() {
    int nod = q.front();
    q.pop();
    in_coada[nod] = false;
    for (auto &nod2:G[nod])
        if (cost[nod] + nod2.second < cost[nod2.first]) {
            cost[nod2.first] = cost[nod] + nod2.second;
            if (!in_coada[nod2.first]) {
                q.push(nod2.first);
                in_coada[nod2.first] = true;
                ct_coada[nod2.first]++;
                if (ct_coada[nod2.first] >= n + 1) {
                    g << "Ciclu negativ!";
                    exit(0);
                }
            }
        }
}

void parcurgere() {
    q.push(1);
    ct_coada[1]=1;
    while (!q.empty())
        element_nou();
}

void afisare() {
    for (int i = 2; i <= n; i++)
        g << cost[i] << ' ';
}

int main() {
    citire();
    initializare();
    parcurgere();
    afisare();
    return 0;
}