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

using namespace std;

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

const int N = 50005;
const int INF = 2000000000;

struct Muchie {
    int varf;
    int cost;
};

Muchie getMuchie (int a, int b)
{
    Muchie m;
    m.varf = a;
    m.cost = b;
    return m;
}

int n, m;
vector <Muchie> graf[N];
queue <int> coada;
int cost[N];
int contor[N];

void read()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        in >> x >> y >> z;
        graf[x].push_back(getMuchie(y, z));
    }
}

bool bfd()
{
    coada.push(1);
    cost[1] = 0;
    while(!coada.empty()) {
        int varfVechi = coada.front();
        coada.pop();
        for (int i = 0; i < graf[varfVechi].size(); i++) {
            if (cost[varfVechi] + graf[varfVechi][i].cost < cost[graf[varfVechi][i].varf])  {
                contor[graf[varfVechi][i].varf]++;
                if (contor[graf[varfVechi][i].varf] > n) {
                    return false;
                }
                cost[graf[varfVechi][i].varf] = cost[varfVechi] + graf[varfVechi][i].cost;
                coada.push(graf[varfVechi][i].varf);
            }
        }
    }
    return true;
}

int main()
{
    read();

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

    if (bfd()) {
        for (int i = 2; i <= n; i++) {
            if (cost[i] == INF) {
                out << "0 ";
            } else {
                out << cost[i] << " ";
            }
        }
        out << "\n";
    } else {
        out << "Ciclu negativ!\n";
    }

    return 0;
}