#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int N = 5e4;
const int M = 25e4;
const int INF = 1 << 30;

vector<int> gr[N + 1];
pair<int, int> edges[M];
queue<int> q;
int d[N + 1], cost[M], cnt[N + 1];
bool in_q[N + 1];

int main() {
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        in >> edges[i].first >> edges[i].second >> cost[i];
        gr[edges[i].first].push_back(i);
    }
    for (int i = 2; i <= n; ++i)
        d[i] = INF;
    int nod;
    q.push(1);
    in_q[1] = cnt[1] = 1;
    while (!q.empty()) {
        nod = q.front();
        q.pop();
        for (auto e : gr[nod]) {
            if (d[nod] + cost[e] < d[edges[e].second]) {
                d[edges[e].second] = d[nod] + cost[e];
                if (!in_q[edges[e].second]) {
                    q.push(edges[e].second);
                    in_q[edges[e].second] = true;
                    if (++cnt[edges[e].second] > n) {
                        out << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        in_q[nod] = false;
    }
    for (int i = 2; i <= n; ++i)
        out << d[i] << ' ';

    in.close();
    out.close();
    return 0;
}