#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> Edge;

int n, m, d[50001], aparitii[50001];
bool viz[50001];
vector<Edge> g[50001];
queue<int> q;
const int INF = 50e6;


int main() {

    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    in >> n >> m;
    for (int i = 1, x, y, c; i <= m; ++i) {
        in >> x >> y >> c;
        g[x].push_back({c, y});
    }

    for (int i = 2; i <= n; ++i) {
        d[i] = INF;
    }
    d[1] = 0;

    q.push(1);

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        viz[x] = false;

        for (int i = 0; i < g[x].size(); ++i) {
            int y = g[x][i].second;
            if (d[x] + g[x][i].first < d[y]) {
                d[y] = d[x] + g[x][i].first;
                if (!viz[y]) {
                    viz[y] = true;
                    q.push(y);
                    if (++aparitii[y] > n) {
                        out << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        out << d[i] << " ";
    }

    return 0;
}