#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;

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

const int NMAX = 50000 + 4;
const int INF = 1000000000;

vector <pair <int ,int> > gr[NMAX];
list <int> coada;
int N, M;
int d[NMAX], decateori[NMAX];
int tata[NMAX], poz[NMAX];
bool viz[NMAX];

bool Bellman(int x0)
{
    for (int i = 1; i <= N; ++i) d[i] = INF;

    int cnt = 1;
    d[x0] = 0;
    coada.push_back(x0);
    poz[x0] = cnt;
    decateori[x0]++;
    viz[x0] = true;
    while (!coada.empty())
    {
        int nod = coada.front();
        coada.pop_front();
        viz[nod] = false;
        poz[nod] = 0;

        if (poz[nod] < poz[tata[nod]]) continue;
        for (int i = 0; i < gr[nod].size(); ++i)
        {
            if (d[gr[nod][i].first] > d[nod] + gr[nod][i].second)
            {
                d[gr[nod][i].first] = gr[nod][i].second + d[nod];

                if (!viz[gr[nod][i].first])
                {
                    decateori[gr[nod][i].first] ++;
                    viz[gr[nod][i].first] = true;
                    coada.push_back(gr[nod][i].first);
                    tata[gr[nod][i].first] = nod;
                    cnt++;
                    poz[gr[nod][i].first] = cnt;
                }

                if (decateori[gr[nod][i].first] > N + 2)
                    {
                        fout << "Ciclu negativ!";
                        return false;
                    }

            }
        }

    }
    return true;

}


int main()
{
fin >> N >> M;
int a, b, c;
for (int i = 1; i <= M; ++i)
{
    fin >>a>>b>>c;
    gr[a].push_back(make_pair (b, c));
   // gr[b].push_back(make_pair (a, c));
}
    if (Bellman(1))
    {
        for (int i =2; i <= N; ++i) fout <<d[i]<<" ";
        return 0 ;

    }

fout << "Ciclu negativ!";
return 0;
}