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


using namespace std;
const int INF(1 << 30);

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

int n, m;
vector< pair<int, int> >graf[50005];
vector <int> v;
queue <int> Q;

int d[50005];
int viz[50005];
bool InQ[50005];

bool bellmanford(int s)
{
    for (int i = 1; i <= n; i++)
    {
        viz[i] = 0;
        InQ[i] = false;
        d[i] = INF;
    }
    d[s] = 0;
    Q.push(s);
    InQ[s] = true;

    while (!Q.empty())
    {
        int nodcurent = Q.front();
        viz[nodcurent]++;
        // algoritmul foloseste un queue cu ajutorul caruia itereaza prin muchii, 
        // in cazul in care nu exista cicluri negative, se v a opri, queueul find vid
        // in cazul in care exista cicluri negative, noduri din sau adiacente cilcului se vor adauga in coada, deci daca traversam un nod de mai mult de n ori, inseamna ca avem un ciclu negativ
        if (viz[nodcurent] >= n)
            return false;
        Q.pop();
        InQ[nodcurent] = false;

        for (size_t i = 0; i < graf[nodcurent].size(); i++)
        {
            int vecin = graf[nodcurent][i].first;
            int cost = graf[nodcurent][i].second;
            if (d[nodcurent] + cost < d[vecin])
            {
                d[vecin] = d[nodcurent] + cost;
                if (!InQ[vecin])
                    Q.push(vecin);
            }
        }
    }
    return true;
}
int main()
{
    // read data
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back({ y, c });
    }
    // bellman-ford
    if (bellmanford(1))
    {
        for (int i = 2; i <= n; i++)
            fout << d[i] << " ";
    }
    else
        fout << "Ciclu negativ!";



    return 0;
}