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

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

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

int a, b, Cost, cont_lant[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)
{

    viz[1] = 1;
    marcare(n);
    _q.push(a);
    int new_nod;
    cont_lant[1] = 1;
    d[1] = 0;
    bool lantNO = 0;
    while (!_q.empty() && !lantNO)
    {
        new_nod = _q.front();
        _q.pop();
        viz[new_nod] = 0;
        //parcurg vecini
        ///for (vector<my_struct>::iterator it = v[nod].begin(); it < v[nod].end(); it++)
        for (int i = 0; i < v[new_nod].size(); i++)
        {
            t = v[new_nod][i];
            if (d[new_nod] + t.cost < d[t.nod])
            {
                d[t.nod] = d[new_nod] + t.cost;
                if (!viz[t.nod])
                {
                    if (cont_lant[t.nod] >0)
                        lantNO = 1;
                    else cont_lant[t.nod]++,viz[t.nod] = 1,_q.push(t.nod);
               
                }
            }

        }
    }
    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);
    }
    if (bell_ford(1))
    {
        g << "Ciclu negativ";
    }
    else {
        for (int i = 2; i <= n; i++)
            g << d[i] << " ";
    }
}