#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define Nmax 50001
using namespace std;

ifstream fin("bellmanford.in"); // putem avea costuri negative => nu merge dijkstra, ci fol bellman-ford
ofstream fout("bellmanford.out"); // bellman-ford detectează existența de circuite negative

// lanţ de la nodul 1 la toate celelalte
int n,m;
vector<pair<int,int>> LA[Nmax]; // lista de adiacenta: LA.first = nodul x ; LA.second = costul de la sursa pana la x;
vector<int> D(Nmax, 1 << 30);   // matricea distantelor minime, initializata cu infinit
vector<int> cnt(Nmax);  // matricea predecesorilor?

vector<int> BellmanFord(int startNod)
{
    D[startNod] = 0; // D pt nodul de start = de la el tot la el => 0
    int are_ciclu = 0;

    // BFS
    queue<int> q;
    vector<bool> viz(Nmax);
    q.push(startNod);

    while(!q.empty() && !are_ciclu) {
        int nodCurent = q.front(); // primul din coada
        q.pop();
        viz[nodCurent] = false;

        for (auto vecin : LA[nodCurent])
        {
            if (D[vecin.first] > D[nodCurent] + vecin.second) // d[v] > d[u] + w(u,v)
            {
                if (!viz[vecin.first])
                {
                    q.push(vecin.first);
                    cnt[vecin.first]++;
                    viz[vecin.first] = true;
                    if (cnt[vecin.first] > n)  // AVEM CICLU;
                    {
                        are_ciclu = 1;
                        // fout << "Ciclu negativ!";
                    }
                }
                D[vecin.first] = D[nodCurent] + vecin.second;
            }
        }
    }
    if (are_ciclu)
        D[startNod] = -1;
    return D;
}


int main()
{
    int x,y,c;
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        LA[x].emplace_back(y, c);
    }

    D = BellmanFord(1);
    if(D[1] == -1){
        fout << "Ciclu negativ!";
        return 0;
    }

    for (int i=2; i<=n; i++)
        fout << D[i] << " ";

    return 0;
}