#include <bits/stdc++.h>

using namespace std;

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

int N, M, x, y, inQ[100005], used[100005], D[100005], c, ok;
vector < pair < int, int > > G[100005];
queue < int > Q;

void bf(int source) {
    memset(D, 62, sizeof(D));
    D[source] = 0;
    inQ[source] = 1;
    Q.push(source);

    while (!Q.empty()) {
        int node = Q.front(); Q.pop();
        inQ[node] = 0;
        ++used[node];

        if (used[node] == N) {
            g << "Ciclu negativ!\n";
            exit(0);
        }

        for (auto it : G[node]) {
            if (D[it.first] > D[node] + it.second) {
                D[it.first] = D[node] + it.second;

                if (!inQ[it.first]) {
                    Q.push(it.first);
                    inQ[it.first] = 1;
                }
            }
        }
    }
}

int main() {
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }

    bf(1);
    for (int i = 2; i <= N; ++i) {
        g << D[i] << ' ';
    }
    return 0;
}