#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];
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 cnt = 1, nod;
    q.push(1);
    in_q[1] = true;
    while (!q.empty() && cnt <= n * m) {
        nod = q.front();
        q.pop();
        in_q[nod] = false;
        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;
                }
            }
        }
        ++cnt;
    }
    bool ok = true;
    for (int i = 0; i < m; ++i)
        if (d[edges[i].first] + cost[i] < d[edges[i].second]) {
            ok = false;
            break;
        }
    if (ok)
        for (int i = 2; i <= n; ++i)
            out << d[i] << ' ';
    else
        out << "Ciclu negativ!";

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