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

using namespace std;

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

const int nmax = 50005, f_mare = 2e9;
int n, m, i, j, x, y ,c, l;
int dist[nmax], viz[nmax];
vector<int> ls[nmax], lc[nmax];
queue <int> q;

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        ls[x].push_back(y);
        lc[x].push_back(c);
    }
    for (i = 2; i <= n; i++)
        dist[i] = f_mare;
    q.push(1);
    while (q.empty() == 0) {
        x = q.front();
        q.pop();
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            c = lc[x][i];

            if (dist[x] + c < dist[y]) {
                dist[y] = dist[x] + c;
                q.push(y);
                viz[y]++;
                if (viz[y] > n) {
                    g << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << dist[i] << ' ';
    return 0;
}