#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 50005;
const int INF = 0x3f3f3f3f;

int N, M;
int q_cnt[N_MAX], dist[N_MAX];
vector <pair <int, int> > graph[N_MAX];
queue <int> q;
bool negative_cycle;
bool in_q[N_MAX];

void read() {
    ifstream fin("bellmanford.in");

    int x, y, c;

    fin >> N >> M;
    while (M--) {
        fin >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }
}

void bellmanford(int node, int cost) {
    if (cost < dist[node]) {
        dist[node] = cost;
        if (!in_q[node]) {
            q.push(node);
            in_q[node] = true;
            ++q_cnt[node];
            if (q_cnt[node] == N) {
                negative_cycle = true;
            }
        }
    }
}

void solve() {
    memset(dist, INF, sizeof dist);

    dist[1] = 0;
    q.push(1);
    in_q[1] = true;
    q_cnt[1] = N - 1;

    while (!q.empty() && !negative_cycle) {
        int node = q.front();
        q.pop();
        in_q[node] = false;
        for (const auto &son : graph[node])
            bellmanford(son.first, dist[node] + son.second);
    }
}

void write() {
    ofstream fout("bellmanford.out");

    if (negative_cycle) {
            fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= N; ++i) {
            fout << dist[i] << " ";
        }
      }
}

int main() {
    read();
    solve();
    write();

    return 0;
}