#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define n_N  50001
queue<int>_q;
int viz[n_N];
int d[n_N];
struct my_struct {

    int nod, cost;
}t, nod_current;
vector<my_struct> v[250022];

int a, b, Cost, Negativ[n_N], n, m;
void marcare(int n)
{
    int k = 10000101;
    for (int i = 1; i <= n; i++)
    {
        d[i] = k;
    }
}
int  bell_ford(int a)
{
    int lantNO = 1;
    _q.push(a);
    viz[a] = 1;
    d[a] = 0;

    int nod_din_coada = 0;
    while (!_q.empty())
    {
        nod_din_coada = _q.front();
        Negativ[nod_din_coada]++;
        viz[nod_din_coada] = 0;
        //de fiecare data cand trecem prin aceset nod-->nod_din_coada crestem un contor pt el si daca am trecut de m
        // cand e cost negativ, revine prin nod_din_coada
        if (Negativ[nod_din_coada] >= n) {
            lantNO = 0;
            break;
        }
        _q.pop();
        for (int i = 0; i < v[nod_din_coada].size(); i++)
        {
            nod_current = v[nod_din_coada][i];
            if (d[nod_din_coada] + nod_current.cost < d[nod_current.nod])
            {
                d[nod_current.nod] = d[nod_din_coada] + nod_current.cost;
                if (!viz[nod_current.nod])
                {
                    _q.push(nod_current.nod);
                    viz[nod_current.nod] = 1;
                }
            }

        }


    }
    return lantNO;
}
int main() {
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> a >> b >> Cost;
        t.nod = b;
        t.cost = Cost;
        v[a].push_back(t);
    }
    marcare(n);
    if (bell_ford(1) == 0)
    {
        g << "Ciclu negativ";
    }
    else {
        for (int i = 2; i <= n; i++)
            g << d[i] << " ";
    }
}