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

using namespace std;

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

const int f_mare = 2e+9;
int n, m, i, x, y, c, l;
vector <int> ls[50003], lc[50003];
queue <int> coada;
bool in_coada[50005];
int cost[50005];
int viz[50005];

int main() {
    f >> n >> m;
    for (i = 2; i <= n; i++)
        cost[i] = f_mare;
    while (m) {
        f >> x >> y >> c;
        ls[x].push_back(y);
        lc[x].push_back(c);
        m--;
    }

    coada.push(1);
    while (!coada.empty()) {
        x = coada.front();
        l = ls[x].size();
        coada.pop();
        in_coada[x] = 0;
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            c = lc[x][i];
            if (cost[x] + c < cost[y]) {
                cost[y] = cost[x] + c;
                if (!in_coada[y]) {
                    in_coada[y] = 1;
                    viz[y]++;
                    coada.push(y);
                    if (viz[y] > n) {
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << cost[i] << ' ';
    return 0;
}