#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_muchii;
    vector <vector <pair <int, int>>> lista_adiacenta;

public:

    void bellman_ford1();
    vector <int> bellman_ford2(const int a)
    {
            int b;
            queue <int> coada;
            vector <bool> m(numar_noduri + 1, false);
            vector <int> v(numar_noduri + 1, 0);
            vector <int> distanta(numar_noduri + 1, INF);

            m[a] = 1;
            distanta[a] = 0;
            coada.push(a);

            while(!coada.empty())
            {
                b = coada.front();
                m[b] = 0;
                coada.pop();

                for(int i = 1; i < lista_adiacenta[b].size(); i++)
                    if(distanta[b] + lista_adiacenta[b][i].second <= distanta[lista_adiacenta[b][i].first])
                {
                    v[lista_adiacenta[b][i].first]++;
                    distanta[lista_adiacenta[b][i].first] = distanta[b] + lista_adiacenta[b][i].second;

                    if(m[lista_adiacenta[b][i].first] == 0)
                    {
                        coada.push(lista_adiacenta[b][i].first);
                        m[lista_adiacenta[b][i].first] = 1;
                    }
                    if(v[lista_adiacenta[b][i].first] >= numar_noduri)
                    {
                        distanta.clear();
                        break;
                    }
                }
            }

    return distanta;
    }
};

void Graf :: bellman_ford1()
{
    int nod1, nod2, cost;
    vector <pair <int, int>> x(1, make_pair(-1, -1));

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i <= numar_noduri + 1; i++)
        lista_adiacenta.push_back(x);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> nod1 >> nod2 >> cost;
        lista_adiacenta[nod1].push_back(make_pair(nod2, cost));
    }

    vector <int> distanta = bellman_ford2(1);

    if(!distanta.size())
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= numar_noduri; i++)
        fout << distanta[i] << " ";
}

int main()
{
    Graf x;
    x.bellman_ford1();

    fin.close();
    fout.close();

    return 0;
}